Functional Analysis
Norms of random submatrices and sparse approximation
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
Tropp, Joel A. 1

1 Applied & Computational Mathematics, California Institute of Technology, Pasadena, CA 91125-5000, USA
@article{CRMATH_2008__346_23-24_1271_0,
     author = {Tropp, Joel A.},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2008.10.008/}
}
TY  - JOUR
AU  - Tropp, Joel A.
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2008.10.008/
DO  - 10.1016/j.crma.2008.10.008
LA  - en
ID  - CRMATH_2008__346_23-24_1271_0
ER  - 
%0 Journal Article
%A Tropp, Joel A.
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2008.10.008/
%R 10.1016/j.crma.2008.10.008
%G en
%F CRMATH_2008__346_23-24_1271_0
Tropp, Joel A. 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. http://www.numdam.org/articles/10.1016/j.crma.2008.10.008/

[1] Bourgain, J.; Tzafriri, L. 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] Buchholz, A. Operator Khintchine inequality in non-commutative probability, Math. Ann., Volume 319 (2001), pp. 1-16

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

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

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

Cited by Sources: