Mean field analysis of sparse reconstruction with correlated variables

Mohammad Ramezanali, Partha P. Mitra, Anirvan M. Sengupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Sparse reconstruction algorithms aim to retrieve high-dimensional sparse signals from a limited number of measurements. A common example is LASSO or Basis Pursuit where sparsity is enforced using an ℓ1-penalty together with a cost function ||y - Hx||22. For random design matrices H, a sharp phase transition boundary separates the 'good' parameter region where error-free recovery of a sufficiently sparse signal is possible and a 'bad' regime where the recovery fails. However, theoretical analysis of phase transition boundary of the correlated variables case lags behind that of uncorrelated variables. Here we use replica trick from statistical physics to show that when an N-dimensional signal x is K-sparse and H is M × N dimensional with the covariance E[Hia Hjb] = 1/M CijDab, with all Daa = 1, the perfect recovery occurs at M ∼ φK(D)K log(N/M) in the very sparse limit, where φK(D) ≥ 1, indicating need for more observations for the same degree of sparsity.

Original languageEnglish (US)
Title of host publication2016 24th European Signal Processing Conference, EUSIPCO 2016
PublisherEuropean Signal Processing Conference, EUSIPCO
Pages1267-1271
Number of pages5
ISBN (Electronic)9780992862657
DOIs
StatePublished - Nov 28 2016
Event24th European Signal Processing Conference, EUSIPCO 2016 - Budapest, Hungary
Duration: Aug 28 2016Sep 2 2016

Publication series

NameEuropean Signal Processing Conference
Volume2016-November
ISSN (Print)2219-5491

Other

Other24th European Signal Processing Conference, EUSIPCO 2016
CountryHungary
CityBudapest
Period8/28/169/2/16

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Electrical and Electronic Engineering

Keywords

  • Basis Pursuit
  • Compressed sensing
  • Replica method
  • Structured matrices

Fingerprint Dive into the research topics of 'Mean field analysis of sparse reconstruction with correlated variables'. Together they form a unique fingerprint.

Cite this