The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
From MaRDI portal
Publication:5346126
DOI10.1109/TIT.2013.2290112zbMath1364.94170arXiv1205.2081WikidataQ59409956 ScholiaQ59409956MaRDI QIDQ5346126
Marc E. Pfetsch, Andreas M. Tillmann
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1205.2081
Related Items
Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery, Modern compressive tomography for quantum information science, Regularity properties for sparse regression, Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery, A General Framework of Rotational Sparse Approximation in Uncertainty Quantification, An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems, A survey on compressive sensing: classical results and recent advancements, 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory, Minimization of $L_1$ Over $L_2$ for Sparse Signal Recovery with Convergence Guarantee, Explicit universal sampling sets in finite vector spaces, Multiple sparse measurement gradient reconstruction algorithm for DOA estimation in compressed sensing, A novel probabilistic approach for vehicle position prediction in free, partial, and full GPS outages, Sparsest representations and approximations of an underdetermined linear system, Cutting Plane Generation through Sparse Principal Component Analysis, A novel regularization based on the error function for sparse recovery, TWO NEW LOWER BOUNDS FOR THE SPARK OF A MATRIX, A primal dual active set with continuation algorithm for the \(\ell^0\)-regularized optimization problem, \(\mathrm{L_1RIP}\)-based robust compressed sensing, Algebraic compressed sensing, Sparse recovery with integrality constraints, Optimal arrangements of classical and quantum states with limited purity, A hierarchical framework for recovery in compressive sensing, A simple homotopy proximal mapping algorithm for compressive sensing, Sampling rates for \(\ell^1\)-synthesis, Block-sparse recovery of semidefinite systems and generalized null space conditions, Effective zero-norm minimization algorithms for noisy compressed sensing, High Dimensional Change Point Estimation via Sparse Projection, Flavors of Compressive Sensing, On a unified view of nullspace-type conditions for recoveries associated with general sparsity structures, Stability analysis of a class of sparse optimization problems, An Introduction to Compressed Sensing, The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty, Stable restoration and separation of approximately sparse signals, Sparse power factorization: balancing peakiness and sample complexity, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, Unnamed Item, Low Complexity Regularization of Linear Inverse Problems, A Scale-Invariant Approach for Sparse Signal Recovery, An effective algorithm for the spark of sparse binary measurement matrices, Phase retrieval for sparse signals, Accuracy guaranties for \(\ell_{1}\) recovery of block-sparse signals, Safe feature elimination for non-negativity constrained convex optimization, Tight bounds on the mutual coherence of sensing matrices for Wigner d-functions on regular grids, Memoryless scalar quantization for random frames, New conditions on stable recovery of weighted sparse signals via weighted \(l_1\) minimization, On the Probabilistic Cauchy Theory for Nonlinear Dispersive PDEs, Structured iterative hard thresholding with on- and off-grid applications, Rank regularized estimation of approximate factor models, Unnamed Item, Exploring chaotic attractors in nonlinear dynamical system under fractal theory, Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit, Preconditioning for orthogonal matching pursuit with noisy and random measurements: the Gaussian case, The Restricted Isometry Property of Subsampled Fourier Matrices, Recovery under side constraints, Sparse recovery of sound fields using measurements from moving microphones, Compressed sensing in the spherical near-field to far-field transformation, Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing, On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels, Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis, Empirical average-case relation between undersampling and sparsity in X-ray CT
