“Compressed” compressed sensing

The field of compressed sensing has shown that a sparse but otherwise arbitrary vector can be recovered exactly from a small number of randomly constructed linear projections (or samples). The question addressed in this paper is whether an even smaller number of samples is sufficient when there exists prior knowledge about the distribution of the unknown vector, or when only partial recovery is needed. An information-theoretic lower bound with connections to free probability theory and an upper bound corresponding to a computationally simple thresholding estimator are derived. It is shown that in certain cases (e.g. discrete valued vectors or large distortions) the number of samples can be decreased. Interestingly though, it is also shown that in many cases no reduction is possible.

• Publication year

  2010

• Venue

  2010 IEEE International Symposium on Information Theory

• Publication date

  2010-01-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ISIT.2010.5513517arXiv 1001.4295
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A note on optimal support recovery in compressed sensing

  2009cited by this paper
• Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

  2008cited by this paper
• Sparse Signal Sampling using Noisy Linear Projections

  2008cited by this paper
• Information Theoretic Bounds for Compressed Sensing

  2008cited by this paper
• Sampling bounds for sparse support recovery in the presence of noise

  2008cited by this paper
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery

  2008cited by this paper
• Fundamental Limits on Sensing Capacity for Sensor Networks and Compressed Sensing

  2008cited by this paper
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007cited by this paper
• Shannon-Theoretic Limits on Noisy Compressive Sampling

  2007cited by this paper
• On sensing capacity of sensor networks for the class of linear observation, fixed SNR models

  2007cited by this paper
• Sharp thresholds for high-dimensional and noisy recovery of sparsity

  2006cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Free Probability Theory and Random Matrices

  2003influential reference
• Asymptotic combinatorics with application to mathematical physics

  2002cited by this paper
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES

  1967cited by this paper

• High-dimensional Bayesian phenotype classification and model selection using genomic predictors

  2019cites this paper
• Convolutional Sparse Coding for Capturing High‐Speed Video Content

  2017cites this paper
• Image Reconstruction from Undersampled Fourier Data Using the Polynomial Annihilation Transform

  2015cites this paper
• Strong convergence of a modified proximal algorithm for solving the lasso

  2015cites this paper
• Monitoring of Electromagnetic Environment along High-Speed Railway Lines Based on Compressive Sensing

  2015cites this paper
• A computational model of pattern separation efficiency in the dentate gyrus with implications in schizophrenia

  2015cites this paper
• The modified accelerated Bregman method for regularized basis pursuit problem

  2014cites this paper
• Bayesian Action&Perception: Representing the World in the Brain

  2014cites this paper
• Overview of Compressed Sensing Approach to CT Image Reconstruction

  2013cites this paper
• Bregman operator splitting with variable stepsize for total variation image reconstruction

  2013cites this paper
• An efficient augmented Lagrangian method with applications to total variation minimization

  2013cites this paper
• Co‐Segmentation of 3D Shapes via Subspace Clustering

  2012cites this paper
• Real-Time Compressive Tracking

  2012cites this paper
• Study on adaptive compressed sensing & reconstruction of quantized speech signals

  2012cites this paper
• Critical Parameter Values and Reconstruction Properties of Discrete Tomography: Application to Experimental Fluid Dynamics

  2012cites this paper
• Object Signature Acquisition through Compressive Scanning

  2012cites this paper
• Optimal compressed sensing reconstructions of fMRI using 2D deterministic and stochastic sampling geometries

  2012cites this paper
• Sparse solutions to random standard quadratic optimization problems

  2012cites this paper
• Open-target sparse sensing of biological agents using DNA microarray

  2011cites this paper
• Multiscale Stochastic Preconditioners in Non-intrusive Spectral Projection

  2011cites this paper
• Bacterial Community Reconstruction Using Compressed Sensing

  2011cites this paper
• Stability and Instance Optimality in Compressed Sensing with Regard to Some Measurement Matrices

  2011cites this paper
• Approximation of Functions of Few Variables in High Dimensions

  2011cites this paper
• Robust and Fast Collaborative Tracking with Two Stage Sparse Optimization

  2010cites this paper
• Fast Optimization for Mixture Prior Models

  2010cites this paper
• A unified approach for minimizing composite norms

  2010cites this paper
• Quantization using compressive sensing

  2010cites this paper
• Convex optimization: a new approach to common challenges in premium rating

  2010cites this paper
• Fundamental Tradeoffs for Sparsity Pattern Recovery

  2010cites this paper
• Fixed point and Bregman iterative methods for matrix rank minimization

  2009cites this paper
• Map-Based Compressive Sensing Model for Wireless Sensor Network Architecture, A Starting Point

  2009cites this paper
• Fast alternating linearization methods for minimizing the sum of two convex functions

  2009cites this paper
• Estimating Human Pose from Occluded Images

  2009cites this paper