Preprint Series 2013

2013:09
V. Temlyakov
We study sparse approximation by greedy algorithms. We prove the Lebesguetype inequalities for the Weak Chebyshev Greedy Algorithm (WCGA), a generalization of the Weak Orthogonal Matching Pursuit to the case of a Banach space. The main novelty of these results is a Banach space setting instead of a Hilbert space ...
[Full Abstract] 
2013:08
V. Temlyakov
Chebyshev Greedy Algorithm is a generalization of the well known Orthogonal Matching Pursuit defined in a Hilbert space to the case of Banach spaces. We apply this algorithm for constructing sparse approximate solutions (with respect to a given dictionary) to convex optimization problems. Rate of convergence results in a ...
[Full Abstract] 
2013:07
K. Ivanov and
P. Petrushev
An iterative algorithm for stable and accurate reconstruction of bandlimited functions from irregular samples on the unit 2d sphere and the general framework of Dirichlet spaces is developed. Geometric rate of convergence in the uniform norm is achieved. It is shown that a MATLAB realization of this algorithms can eff ...
[Full Abstract] 
2013:06
A. Dove,
J. Griggs,
R. Kang, and
J. Sereni
We seek families of subsets of an $n$set of given size that contain the fewest $k$chains. We prove a "supersaturationtype" extension of both Sperner's Theorem (1928) and its generalization by Erdős (1945). Erdős showed that a largest $k$chain free family in the Boolean lattice is formed ...
[Full Abstract] 
2013:05
K. Ivanov and
P. Petrushev
A method for fast evaluation of bandlimited functions (spherical polynomials) at many scattered points on the unit 2d sphere is presented. The method relies on the superb localization of the father needlet kernels and their compatibility with spherical harmonics. It is fast, local, memory efficient, numerically stable and with ...
[Full Abstract] 
2013:04
S. Dekel,
G. Kerkyacharian,
G. Kyriazis, and
P. Petrushev
A small perturbation method is developed and deployed to the construction of compactly supported frames for Besov and TriebelLizorkin in the general setting of Dirichlet space with a doubling measure and local scaleinvariant Poincaré inequality. This allows, in particular, to develop compactly supported frames for Besov and TriebelLizorkin spaces ...
[Full Abstract] 
2013:03
E. Livshitz and
V. Temlyakov
We study sparse approximation by greedy algorithms. Our contribution is twofold. First, we prove exact recovery with high probability of random $K$sparse signals within $\lceil K(1+\epsilon)\rceil$ iterations of the Orthogonal Matching Pursuit (OMP). This result shows that in a probabilistic sense the OMP is almost optimal ...
[Full Abstract] 
2013:02
V. Temlyakov
We prove an inequality for the entropy numbers in terms of nonlinear Kolmogorov's widths. This inequality is in a spirit of known inequalities of this type and it is adjusted to the form convenient in applications for mterm approximations with respect to a given system. Also, we obtain ...
[Full Abstract] 
2013:01
V. Temlyakov
We discuss construction of coverings of the unit ball of a finite dimensional Banach space. The well known technique of comparing volumes gives upper and lower bounds on covering numbers. This technique does not provide a construction of good coverings. Here we apply incoherent dictionaries for construction of good coverings ...
[Full Abstract]