Comptes Rendus
no. 23-24
Functional Analysis
Norms of random submatrices and sparse approximation

Presented by: Yves Meyer

Joel A. Tropp1
1 Applied & Computational Mathematics, California Institute of Technology, Pasadena, CA 91125-5000, USA
Comptes Rendus. Mathématique, Volume 346 (2008) no. 23-24, pp. 1271-1274.

Many problems in the theory of sparse approximation require bounds on operator norms of a random submatrix drawn from a fixed matrix. The purpose of this Note is to collect estimates for several different norms that are most important in the analysis of ℓ1 minimization algorithms. Several of these bounds have not appeared in detail.

De nombreux problèmes en théorie de l'approximation non linéaire exigent des majorations la norme d'une matrice aléatoirement extraite d'une matrice donnée de plus grande dimension. L'objectif de cette Note est de présenter des estimations de ces normes qui se révèlent être importantes pour l'étude des algorithmes de minimisation de type ℓ1. La plupart de ces bornes n'ont pas encore été publiées explicitement.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2008.10.008

Joel A. Tropp 1

1 Applied & Computational Mathematics, California Institute of Technology, Pasadena, CA 91125-5000, USA 
@article{CRMATH_2008__346_23-24_1271_0,
     author = {Joel A. Tropp},
     title = {Norms of random submatrices and sparse approximation},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1271--1274},
     publisher = {Elsevier},
     volume = {346},
     number = {23-24},
     year = {2008},
     doi = {10.1016/j.crma.2008.10.008},
     language = {en},
}
TY  - JOUR
AU  - Joel A. Tropp
TI  - Norms of random submatrices and sparse approximation
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 1271
EP  - 1274
VL  - 346
IS  - 23-24
PB  - Elsevier
DO  - 10.1016/j.crma.2008.10.008
LA  - en
ID  - CRMATH_2008__346_23-24_1271_0
ER  - 
%0 Journal Article
%A Joel A. Tropp
%T Norms of random submatrices and sparse approximation
%J Comptes Rendus. Mathématique
%D 2008
%P 1271-1274
%V 346
%N 23-24
%I Elsevier
%R 10.1016/j.crma.2008.10.008
%G en
%F CRMATH_2008__346_23-24_1271_0
Joel A. Tropp. Norms of random submatrices and sparse approximation. Comptes Rendus. Mathématique, Volume 346 (2008) no. 23-24, pp. 1271-1274. doi : 10.1016/j.crma.2008.10.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2008.10.008/

[1] J. Bourgain; L. Tzafriri Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J. Math., Volume 57 (1987) no. 2, pp. 137-224

[2] A. Buchholz Operator Khintchine inequality in non-commutative probability, Math. Ann., Volume 319 (2001), pp. 1-16

[3] M. Ledoux; M. Talagrand Probability in Banach Spaces: Isoperimetry and Processes, Springer, 1991

[4] M. Rudelson; R. Vershynin Sampling from large matrices: An approach through geometric functional analysis, J. Assoc. Comput. Mach., Volume 54 (2007) no. 4, pp. 1-19

[5] J.A. Tropp The random paving property for uniformly bounded matrices, Studia Math., Volume 185 (2008) no. 1, pp. 67-82

Cited by Sources:

Comments - Policy