no. 23-24
Functional Analysis
Norms of random submatrices and sparse approximation
[Normes de sous-matrices aléatoires et approximation creuse]

Présenté par : Yves Meyer

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

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.

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.

Reçu le :
Accepté le :
Publié le :
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, Tome 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

Cité par Sources :