Greedy Approximation

Cover......Page 1
20 Greedy Approximation......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 11
1.1 Introduction......Page 17
1.2 Schauder bases in Banach spaces......Page 22
1.3 Greedy bases......Page 31
1.4 Quasi-greedy and almost greedy bases......Page 49
1.5 Weak Greedy Algorithms with respect to bases......Page 55
1.6 Thresholding and minimal systems......Page 59
1.7 Greedy approximation with respect to the trigonometric system......Page 63
1.8 Greedy-type bases; direct and inverse theorems......Page 74
1.9 Some further results......Page 79
1.10 Systems Lp-equivalent to the Haar basis......Page 84
1.11 Open problems......Page 92
2.1 Introduction......Page 93
2.2 Convergence......Page 100
2.3.1 Upper bounds for approximation by general dictionaries......Page 105
2.3.2 Upper estimates for weak-type greedy algorithms......Page 110
2.4 Greedy algorithms for systems that are not dictionaries......Page 113
2.5 Greedy approximation with respect to λ-quasi-orthogonal dictionaries......Page 117
2.6.1 Introduction......Page 127
2.6.2 Proofs......Page 132
2.7.1 Saturation of the Pure Greedy Algorithm......Page 138
2.7.2 A generalization of the Pure Greedy Algorithm......Page 141
2.7.3 Performance of the n-Greedy Algorithm with regard to an incoherent dictionary......Page 145
2.8 Some further remarks......Page 151
2.9 Open problems......Page 157
3.1 Introduction: definitions and some simple properties......Page 159
3.2 Finite dimensional spaces......Page 160
3.3.1 Univariate trigonometric polynomials......Page 167
3.3.2 Multivariate trigonometric polynomials......Page 172
The Dirichlet kernels.......Page 173
The de la Vallée Poussin kernels.......Page 174
3.3.3 Volume estimates; generalized Rudin–Shapiro polynomials......Page 175
3.4 The function classes......Page 181
3.5 General inequalities......Page 184
3.6 Some further remarks......Page 191
3.7 Open problems......Page 198
4.1.2 Statistics; regression theory......Page 199
4.1.3 Learning theory......Page 200
4.2.1 The measure theory and integration......Page 205
4.2.2 The concentration of measure inequalities......Page 212
4.2.3 The Kullback–Leibler information and the Hellinger distance......Page 217
4.3.1 Introduction......Page 222
4.3.2 First estimates for classes from Sr......Page 225
4.3.3 Further estimates for classes from Sr; chaining technique......Page 229
4.3.4 Least squares estimators for convex hypothesis spaces......Page 235
4.3.5 Least squares estimators for non-convex hypothesis spaces......Page 239
4.3.6 Estimates for classes from Sr2......Page 242
4.3.7 Estimates for classes from Sr1......Page 249
4.4.1 Introduction......Page 251
4.4.2 The least squares estimators......Page 256
4.4.3 Some examples......Page 264
4.5.1 Introduction......Page 269
4.5.2 The projection learning......Page 271
4.5.3 Lower estimates for the Bernoulli scheme......Page 275
4.5.4 The proper function learning......Page 280
4.6 Application of greedy algorithms in learning theory......Page 286
5.1 Introduction......Page 293
(T2) approximate recovery.......Page 294
(M2) greedy algorithm.......Page 295
5.2 Equivalence of three approximation properties of the compressed sensing matrix......Page 299
5.3.1 Construction of a good subspace......Page 303
5.3.2 Duality principle......Page 307
5.4 Dealing with noisy data......Page 310
5.5 First results on exact recovery of sparse signals; the Orthogonal Greedy Algorithm......Page 314
5.6 Exact recovery of sparse signals; the Subspace Pursuit Algorithm......Page 321
5.7.1 Introduction......Page 330
5.7.2 Upper bounds......Page 332
5.7.3 Lower bounds; probabilistic approach......Page 335
5.7.4 Lower bounds; deterministic construction......Page 337
5.7.5 Dictionaries with the RIP......Page 339
5.7.6 Incoherence and the Kolmogorov widths......Page 340
5.8 Restricted Isometry Property for random matrices......Page 343
5.9 Some further remarks......Page 346
5.10 Open problems......Page 348
6.1 Introduction......Page 350
6.2 The Weak Chebyshev Greedy Algorithm......Page 356
6.3 Relaxation; co-convex approximation......Page 363
6.4 Free relaxation......Page 366
6.5 Fixed relaxation......Page 370
6.6 Thresholding algorithms......Page 375
6.7.1 Introduction......Page 379
6.7.2 Convergence of the Dual-Based Expansion......Page 382
6.7.3 Modification of the Weak Dual Greedy Algorithm......Page 386
6.7.4 Convergence of the WDGA......Page 391
6.8 Relaxation; X-greedy algorithms......Page 394
6.9 Incoherent dictionaries and exact recovery......Page 397
6.10 Greedy algorithms with approximate evaluations and restricted search......Page 401
6.11 An application of greedy algorithms for the discrepancy estimates......Page 406
6.12 Open problems......Page 420
References......Page 421
Index......Page 431