IMPROVED BOUNDS FOR SPARSE RECOVERY FROM SUBSAMPLED RANDOM CONVOLUTIONS

• 成果类型: Article
• 署名作者: Mendelson, Shahar; Rauhut, Holger; Ward, Rachel
• 署名单位: Technion Israel Institute of Technology; Australian National University; RWTH Aachen University; University of Texas System; University of Texas Austin
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/18-AAP1391
• 发表日期: 2018
• 页码: 3491-3527
• 关键词: restricted isometry property; reconstruction; matrices; projections; Operators; dimension; geometry

摘要

We study the recovery of sparse vectors from subsampled random convolutions via l(1)-minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a sub-Gaussian generator with independent entries, we improve previously known estimates: if the sparsity s is small enough, that is, s less than or similar to root n/log(n), we show that m greater than or similar to s log(en/s) measurements are sufficient to recover s-sparse vectors in dimension n with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If s is larger, then essentially m >= s log(2)(s) log(log(s)) log(n) measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques which should be of independent interest.