Resolution Limits of Sparse Coding in High Dimensions
Alyson Fletcher
UC-Berkeley

T46

Sundeep Rangan
Qualcomm

Vivek Goyal
MIT
d

Estimation problem: Detect sparsity pattern of x from y

x  Rn
k-sparse vector

A  R m× n

y  Rm

Estimator

^ x

Random matrix

· Recent results characterize performance of simple convex programming-based estimators (e.g. basis pursuit, lasso) · Basic questions: Can we do better with more computation? Is even this much computation warranted? · Main results: · Optimal algorithm, lasso, and trivial algorithm all give the same dependence of measurements m on signal length n and sparsity k · Differences emerge from dependence on signal-to-noise ratio and spread in sizes of nonzero entries of x