On the conditioning of random subdictionaries

DOI10.1016/J.ACHA.2007.09.001zbMath1143.15026OpenAlexW2020775053WikidataQ59750757 ScholiaQ59750757MaRDI QIDQ930731

Joel A. Tropp

Publication date: 1 July 2008

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.acha.2007.09.001

zbMATH Keywords

convex optimizationregularizationcoherenceuncertainty principlerandom matrixsparsityunderdetermined linear systembasis pursuitdictionaryBanach space probability

Mathematics Subject Classification ID

Convex programming (90C25) Random matrices (algebraic aspects) (15B52) Linear equations (linear algebraic aspects) (15A06) Probability theory on linear topological spaces (60B11)

Related Items (29)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Deterministic convolutional compressed sensing matrices ⋮ Kesten-McKay law for random subensembles of Paley equiangular tight frames ⋮ A Short Introduction to Optimal Line Packings ⋮ Full spark frames ⋮ The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach ⋮ Norms of structured random matrices ⋮ Non-commutative Khinchine-type inequality for dependent random variables and overview of its applications in data science ⋮ Two are better than one: fundamental parameters of frame coherence ⋮ BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING ⋮ Improving the Incoherence of a Learned Dictionary via Rank Shrinkage ⋮ Discrete uncertainty principles and sparse signal processing ⋮ Convergence radius and sample complexity of ITKM algorithms for dictionary learning ⋮ A Gradient-Enhanced L1 Approach for the Recovery of Sparse Trigonometric Polynomials ⋮ Generalized sampling and infinite-dimensional compressed sensing ⋮ Stable restoration and separation of approximately sparse signals ⋮ User-friendly tail bounds for sums of random matrices ⋮ Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices ⋮ Sparsity in time-frequency representations ⋮ Construction of highly redundant incoherent unit norm tight frames as a union of orthonormal bases ⋮ Moment inequalities for matrix-valued U-statistics of order 2 ⋮ Packings in Real Projective Spaces ⋮ On the linear independence of spikes and sines ⋮ Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms ⋮ On the identifiability of overcomplete dictionaries via the minimisation principle underlying K-SVD ⋮ Random sampling of sparse trigonometric polynomials. II: Orthogonal matching pursuit versus basis pursuit ⋮ IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM ⋮ Submatrices with NonUniformly Selected Random Supports and Insights into Sparse Approximation ⋮ Preconditioning for orthogonal matching pursuit with noisy and random measurements: the Gaussian case

Uses Software

• PDCO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the linear independence of spikes and sines
• On singular values of matrices with independent rows
• A simple proof of the restricted isometry property for random matrices
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Random vectors in the isotropic position
• Grassmannian frames with applications to coding and communication
• Quantitative robust uncertainty principles and optimally sparse decompositions
• Uncertainty Principles and Signal Recovery
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Compressed sensing and best 𝑘-term approximation
• Sampling convex bodies: a random matrix approach
• On sparse reconstruction from Fourier and Gaussian measurements
• Sampling from large matrices
• On Sparse Representations in Arbitrary Redundant Bases
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Sparse representations in unions of bases
• Recovery of Short, Complex Linear Combinations Via<tex>$ell _1$</tex>Minimization
• Just relax: convex programming methods for identifying sparse signals in noise
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Random sets of isomorphism of linear operators on Hilbert space
• The best constants in the Khintchine inequality
• Atomic Decomposition by Basis Pursuit
• Random walks and anO*(n5) volume algorithm for convex bodies
• Uncertainty principles and ideal atomic decomposition
• A generalized uncertainty principle and sparse representation in pairs of bases
• Sparse Approximate Solutions to Linear Systems
• The Khintchine inequalities and martingale expanding sphere of their action
• The random paving property for uniformly bounded matrices
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Operator Khintchine inequality in non-commutative probability
• Adaptive greedy approximations

This page was built for publication: On the conditioning of random subdictionaries