On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

Abstract

We consider the synthesis problem of Compressed Sensing - given s and an MXn matrix A, extract from it an mXn submatrix A', certified to be s-good, with m as small as possible. Starting from the verifiable sufficient conditions of s-goodness, we express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm. We propose randomized algorithms for efficient construction of rank k approximation of matrices of size mXn achieving accuracy bounds O(1)sqrt({ln(mn)/k) which hold in expectation or with high probability. We also supply derandomized versions of the approximation algorithms which does not require random sampling of matrices and attains the same accuracy bounds. We further demonstrate that our algorithms are optimal up to the logarithmic in m and n factor. We provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

References in corpus (1)

• Discussion: The Dantzig selector: Statistical estimation when $p$ is much larger than $n$

Cited by in corpus (25)

• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• A weighted L1-minimization approach for sparse polynomial chaos expansions
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• RIPless compressed sensing from anisotropic measurements
• On Polynomial Chaos Expansion via Gradient-enhanced ${\ell }_1$-minimization
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values
• RSP-Based Analysis for Sparsest and Least ${\ell }_1$-Norm Solutions to Underdetermined Linear Systems
• Unknown sparsity in compressed sensing: Denoising and inference
• Block-length dependent thresholds in block-sparse compressed sensing
• Accuracy guarantees for L1-recovery
• Low-Cost and High-Throughput Testing of COVID-19 Viruses and Antibodies via Compressed Sensing: System Concepts and Computational Experiments
• Estimating Unknown Sparsity in Compressed Sensing
• Accuracy guaranties for ${\ell }_1$ recovery of block-sparse signals
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• On a class of optimization-based robust estimators
• A Class of Novel STAP Algorithms Using Sparse Recovery Technique
• On the Certification of the Restricted Isometry Property
• Sparse Recovery, Kashin Decomposition and Conic Programming
• From variable density sampling to continuous sampling using Markov chains
• Hidden cliques and the certification of the restricted isometry property
• Locally Sparse Reconstruction Using the ${\ell }^{1,\infty }$-Norm
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• Optimality of ${\ell }_2/{\ell }_1$-optimization block-length dependent thresholds
• Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
• Faster $p$-Norm Regression Using Sparsity