Comptes Rendus
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

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.

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

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

  • Asaf Ferber; Jie Han; Dingjia Mao; Roman Vershynin Hamiltonicity of sparse pseudorandom graphs, Combinatorics, Probability and Computing (2025), p. 1 | DOI:10.1017/s0963548325000070
  • Stanislav Minsker; Yiqiu Shen The impact of contamination and correlated design on the Lasso: An average case analysis, Statistics Probability Letters, Volume 223 (2025), p. 110417 | DOI:10.1016/j.spl.2025.110417
  • Rajarshi Bhattacharjee; Gregory Dexter; Petros Drineas; Cameron Musco; Archan Ray Sublinear Time Eigenvalue Approximation via Random Sampling, Algorithmica, Volume 86 (2024) no. 6, p. 1764 | DOI:10.1007/s00453-024-01208-5
  • Radosław Adamczak; Joscha Prochno; Marta Strzelecka; Michał Strzelecki Norms of structured random matrices, Mathematische Annalen, Volume 388 (2024) no. 4, p. 3463 | DOI:10.1007/s00208-023-02599-6
  • Marie-Christine Pali; Simon Ruetz; Karin Schnass Average Performance of OMP and Thresholding Under Dictionary Mismatch, IEEE Signal Processing Letters, Volume 29 (2022), p. 1077 | DOI:10.1109/lsp.2022.3167313
  • Pradip Sasmal; Chandra R. Murthy Incoherence is Sufficient for Statistical RIP of Unit Norm Tight Frames: Constructions and Properties, IEEE Transactions on Signal Processing, Volume 69 (2021), p. 2343 | DOI:10.1109/tsp.2021.3066777
  • Simon Ruetz; Karin Schnass Submatrices with NonUniformly Selected Random Supports and Insights into Sparse Approximation, SIAM Journal on Matrix Analysis and Applications, Volume 42 (2021) no. 3, p. 1268 | DOI:10.1137/20m1386384
  • Ainesh Bakshi; Nadiia Chepurko; Rajesh Jayaram, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (2020), p. 1191 | DOI:10.1109/focs46700.2020.00114
  • Elizaveta Rebrova; Deanna Needell, 2019 53rd Asilomar Conference on Signals, Systems, and Computers (2019), p. 271 | DOI:10.1109/ieeeconf44664.2019.9048928
  • Stéphane Chrétien; Sébastien Darses On a new method for controlling the entire spectrum in the problem of column subset selection, Expositiones Mathematicae, Volume 37 (2019) no. 3, p. 314 | DOI:10.1016/j.exmath.2019.02.002
  • Pradip Sasmal; Phanindra Jampana; C.S. Sastry Construction of highly redundant incoherent unit norm tight frames as a union of orthonormal bases, Journal of Complexity, Volume 54 (2019), p. 101401 | DOI:10.1016/j.jco.2019.03.001
  • Wei Huang; Lu Liu; Zhuo Yang; Yao Zhao Sparse signal recovery via non-convex optimization and overcomplete dictionaries, International Journal of Wavelets, Multiresolution and Information Processing, Volume 16 (2018) no. 06, p. 1850058 | DOI:10.1142/s0219691318500583
  • Stéphane Chrétien; Olivier Ho Feature Selection in Weakly Coherent Matrices, Latent Variable Analysis and Signal Separation, Volume 10891 (2018), p. 127 | DOI:10.1007/978-3-319-93764-9_13
  • Stéphane Chrétien; Sébastien Darses An Elementary Approach to the Problem of Column Selection in a Rectangular Matrix, Machine Learning, Optimization, and Big Data, Volume 10710 (2018), p. 234 | DOI:10.1007/978-3-319-72926-8_20
  • Maria Segovia; Islam Rohouma; Qiteng Hong; Stephane Chretien; Paul Clarkson, 2017 IEEE International Workshop on Applied Measurements for Power Systems (AMPS) (2017), p. 1 | DOI:10.1109/amps.2017.8078349
  • Xin Ding; Wei Chen; Ian J. Wassell Joint Sensing Matrix and Sparsifying Dictionary Optimization for Tensor Compressive Sensing, IEEE Transactions on Signal Processing, Volume 65 (2017) no. 14, p. 3632 | DOI:10.1109/tsp.2017.2699639
  • Waheed U. Bajwa; Marco F. Duarte; Robert Calderbank Conditioning of Random Block Subdictionaries With Applications to Block-Sparse Recovery and Regression, IEEE Transactions on Information Theory, Volume 61 (2015) no. 7, p. 4060 | DOI:10.1109/tit.2015.2429632
  • Alexander Barg; Arya Mazumdar; Rongrong Wang Restricted Isometry Property of Random Subdictionaries, IEEE Transactions on Information Theory, Volume 61 (2015) no. 8, p. 4440 | DOI:10.1109/tit.2015.2448658
  • Deanna Needell; Ran Zhao; Anastasios Zouzias Randomized block Kaczmarz method with projection for solving least squares, Linear Algebra and its Applications, Volume 484 (2015), p. 322 | DOI:10.1016/j.laa.2015.06.027
  • Charles Dossal; Remi Tesson Consistency ofℓ1recovery from noisy deterministic measurements, Applied and Computational Harmonic Analysis, Volume 36 (2014) no. 3, p. 508 | DOI:10.1016/j.acha.2013.08.001
  • Ayca Ozcelikkale; Serdar Yuksel; Haldun M. Ozaktas Unitary Precoding and Basis Dependency of MMSE Performance for Gaussian Erasure Channels, IEEE Transactions on Information Theory, Volume 60 (2014) no. 11, p. 7186 | DOI:10.1109/tit.2014.2354034
  • Stephane Chretien; Sebastien Darses Sparse Recovery With Unknown Variance: A LASSO-Type Approach, IEEE Transactions on Information Theory, Volume 60 (2014) no. 7, p. 3970 | DOI:10.1109/tit.2014.2301162
  • Deanna Needell; Joel A. Tropp Paved with good intentions: Analysis of a randomized block Kaczmarz method, Linear Algebra and its Applications, Volume 441 (2014), p. 199 | DOI:10.1016/j.laa.2012.12.022
  • Simon Foucart; Holger Rauhut Advanced Tools from Probability Theory, A Mathematical Introduction to Compressive Sensing (2013), p. 201 | DOI:10.1007/978-0-8176-4948-7_8
  • Simon Foucart; Holger Rauhut Recovery of Random Signals using Deterministic Matrices, A Mathematical Introduction to Compressive Sensing (2013), p. 459 | DOI:10.1007/978-0-8176-4948-7_14
  • Marco F. Duarte; Sina Jafarpour; A. Robert Calderbank Performance of the Delsarte-Goethals Frame on Clustered Sparse Vectors, IEEE Transactions on Signal Processing, Volume 61 (2013) no. 8, p. 1998 | DOI:10.1109/tsp.2013.2242064
  • Charles Dossal; Marie-Line Chabanol; Gabriel Peyré; Jalal Fadili Sharp support recovery from noisy random measurements byℓ1-minimization, Applied and Computational Harmonic Analysis, Volume 33 (2012) no. 1, p. 24 | DOI:10.1016/j.acha.2011.09.003
  • Waheed U. Bajwa; Robert Calderbank; Dustin G. Mixon Two are better than one: Fundamental parameters of frame coherence, Applied and Computational Harmonic Analysis, Volume 33 (2012) no. 1, p. 58 | DOI:10.1016/j.acha.2011.09.005
  • Patrick Kuppinger; Giuseppe Durisi; Helmut Bolcskei Uncertainty Relations and Sparse Signal Recovery for Pairs of General Signal Sets, IEEE Transactions on Information Theory, Volume 58 (2012) no. 1, p. 263 | DOI:10.1109/tit.2011.2167215
  • Antony Joseph; Andrew R Barron Least Squares Superposition Codes of Moderate Dictionary Size Are Reliable at Rates up to Capacity, IEEE Transactions on Information Theory, Volume 58 (2012) no. 5, p. 2541 | DOI:10.1109/tit.2012.2184847
  • Stéphane Chrétien; Sébastien Darses Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality, Statistics Probability Letters, Volume 82 (2012) no. 7, p. 1479 | DOI:10.1016/j.spl.2012.03.038
  • Joel A. Tropp, 2010 44th Annual Conference on Information Sciences and Systems (CISS) (2010), p. 1 | DOI:10.1109/ciss.2010.5464824
  • Waheed U. Bajwa; Robert Calderbank; Sina Jafarpour, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2010), p. 977 | DOI:10.1109/allerton.2010.5707015
  • Joel A. Tropp; Jason N. Laska; Marco F. Duarte; Justin K. Romberg; Richard G. Baraniuk Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals, IEEE Transactions on Information Theory, Volume 56 (2010) no. 1, p. 520 | DOI:10.1109/tit.2009.2034811
  • Waheed U. Bajwa; Robert Calderbank; Sina Jafarpour Why Gabor frames? Two fundamental measures of coherence and their role in model selection, Journal of Communications and Networks, Volume 12 (2010) no. 4, p. 289 | DOI:10.1109/jcn.2010.6388466
  • Joel A Tropp; Stephen J Wright Computational Methods for Sparse Solution of Linear Inverse Problems, Proceedings of the IEEE, Volume 98 (2010) no. 6, p. 948 | DOI:10.1109/jproc.2010.2044010
  • Justin Romberg Compressive Sensing by Random Convolution, SIAM Journal on Imaging Sciences, Volume 2 (2009) no. 4, p. 1098 | DOI:10.1137/08072975x
  • Emmanuel J. Candès; Yaniv Plan Near-ideal model selection by ℓ1 minimization, The Annals of Statistics, Volume 37 (2009) no. 5A | DOI:10.1214/08-aos653

Cité par 38 documents. Sources : Crossref

Commentaires - Politique

Il n'y a aucun commentaire pour cet article. Soyez le premier à écrire un commentaire !

Publier un nouveau commentaire:

Publier une nouvelle réponse: