Mario Ullrich, Jan Vybíral
For $\varepsilon\in(0,1/2)$ and a natural number $d\ge 2$, let $N$ be a natural number with \[ N \,\ge\, 2^9\,\log_2(d)\, \left(\frac{\log_2(1/\varepsilon)}{\varepsilon}\right)^2. \] We prove that there is a set of $N$ points in the unit cube $[0,1]^d$, which intersects all axis-parallel boxes with volume $\varepsilon$. That is, the dispersion of this point set is bounded from above by $\varepsilon$.
Jan Vybíral
We introduce the concept of average best $m$-term approximation widths with respect to a probability measure on the unit ball of $\ell_p^n$. We estimate these quantities for the embedding $id:\ell_p^n\to\ell_q^n$ with $0<p\le q\le \infty$ for the normalized cone and surface measure. Furthermore, we consider certain tensor product weights and show that a typical vector with respect to such a measure exhibits a strong compressible (i.e. nearly sparse) structure.
Massimo Fornasier, Jan Vybíral, Ingrid Daubechies
We address the structure identification and the uniform approximation of sums of ridge functions $f(x)=\sum_{i=1}^m g_i(a_i\cdot x)$ on ${\mathbb R}^d$, representing a general form of a shallow feed-forward neural network, from a small number of query samples. Higher order differentiation, as used in our constructive approximations, of sums of ridge functions or of their compositions, as in deeper neural network, yields a natural connection between neural network weight identification and tensor product decomposition identification. In the case of the shallowest feed-forward neural network, second order differentiation and tensors of order two (i.e., matrices) suffice as we prove in this paper. We use two sampling schemes to perform approximate differentiation - active sampling, where the sampling points are universal, actively, and randomly designed, and passive sampling, where sampling points were preselected at random from a distribution with known density. Based on multiple gathered approximated first and second order differentials, our general approximation strategy is developed as a sequence of algorithms to perform individual sub-tasks. We first perform an active subspace search by approximating the span of the weight vectors $a_1,\dots,a_m$. Then we use a straightforward substitution, which reduces the dimensionality of the problem from $d$ to $m$. The core of the construction is then the stable and efficient approximation of weights expressed in terms of rank-$1$ matrices $a_i \otimes a_i$, realized by formulating their individual identification as a suitable nonlinear program. We prove the successful identification by this program of weight vectors being close to orthonormal and we also show how we can costructively reduce to this case by a whitening procedure, without loss of any generality.
Anton Kolleck, Jan Vybíral
Support Vector Machines (SVM) with $\ell_1$ penalty became a standard tool in analysis of highdimensional classification problems with sparsity constraints in many applications including bioinformatics and signal processing. Although SVM have been studied intensively in the literature, this paper has to our knowledge first non-asymptotic results on the performance of $\ell_1$-SVM in identification of sparse classifiers. We show that a $d$-dimensional $s$-sparse classification vector can be (with high probability) well approximated from only $O(s\log(d))$ Gaussian trials. The methods used in the proof include concentration of measure and probability in Banach spaces.