Lower bounds for adaptive sparse recovery

DOI10.1137/1.9781611973105.47MaRDI QIDQ5741755zbMATH OpenOpenAlexFDO

Authors Eric Price, David P. Woodruff

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.3518

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector $xin{R}^n$ from $m$ linear measurements $A_{1}x,\mathrm{...},A_{m}x$. One may choose each vector $A_i$ based on $A_{1}x,\mathrm{...},A_{i-1}x$, and must output $x\ast$ satisfying |x* - x|_p leq (1 + epsilon) min_{k ext{-sparse} x'} |x - x'|_p with probability at least $1-delta>2/3$, for some $pin1,2$. For $p=2$, it was recently shown that this is possible with $m=O(frac1epsilonkloglog(n/k))$, while nonadaptively it requires $Theta(frac1epsilonklog(n/k))$. It is also known that even adaptively, it takes $m=Omega(k/epsilon)$ for $p=2$. For $p=1$, there is a non-adaptive upper bound of $ildeO(frac1sqrtepsilonklogn)$. We show: * For $p=2$, $m=Omega(loglogn)$. This is tight for $k=O(1)$ and constant $epsilon$, and shows that the $loglogn$ dependence is correct. * If the measurement vectors are chosen in $R$ "rounds", then $m=Omega(Rlo{g}^{1/R}n)$. For constant $epsilon$, this matches the previously known upper bound up to an O(1) factor in $R$. * For $p=1$, $m=Omega(k/(sqrtepsiloncdotlogk/epsilon))$. This shows that adaptivity cannot improve more than logarithmic factors, providing the analog of the $m=Omega(k/epsilon)$ bound for $p=2$.

Recommendations

• Adaptive sparse recovery with limited adaptivity
• Improved algorithms for adaptive compressed sensing
• Lower bounds for sparse recovery
• \(\ell _{2}/\ell _{2}\)-foreach sparse recovery with low risk
• Simple bounds for recovering low-complexity models

Cited in

(15)

• Recovering block-structured activations using compressive measurements
• Sequential adaptive compressed sampling via Huffman codes
• Performance Guarantees for Adaptive Estimation of Sparse Signals
• Online Adaptive Estimation of Sparse Signals: Where RLS Meets the $\ell_1$-Norm
• Computable Performance Bounds on Sparse Recovery
• Adaptive sensing performance lower bounds for sparse signal detection and support estimation
• Improved algorithms for adaptive compressed sensing
• Querying a Matrix Through Matrix-Vector Products.
• Adaptive sparse recovery with limited adaptivity
• \(\ell _{2}/\ell _{2}\)-foreach sparse recovery with low risk
• Lower bounds for sparse recovery
• Randomized approximation of summable sequences -- adaptive and non-adaptive
• Uniform approximation of vectors using adaptive randomized information
• A combinatorial approach to robust PCA
• Multipass linear sketches for geometric LP-type problems

This page was built for publication: Lower bounds for adaptive sparse recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741755)