A Proof of Conjecture on Restricted Isometry Property Constants δtk (0 < t < 4/3)

作者：Zhang, Rui^*; Li, Song

来源：IEEE Transactions on Information Theory, 2018, 64(3): 1699-1705.

DOI：10.1109/TIT.2017.2705741

• Compressed sensing
• l(1)-norm minimization
• Restricted isometry property constant
• Sparse signal recovery

In this paper, we give a complete answer to the conjecture on restricted isometry property (RIP) constants delta(tk) (0 < t < (4/3)), which was proposed by T. Cai and A. Zhang. We have shown that when 0 < t < (4/3), the condition delta(tk) < (t/(4-t)) is sufficient to guarantee the exact recovery for all k-sparse signals in the noiseless case via the constrained l(1)-norm minimization. These bounds are sharp in the sense that for any epsilon > 0, delta(tk) < (t/(4-t)) + epsilon cannot guarantee the exact recovery of some k-sparse signals. Furthermore, it will be shown that similar characterizations also hold for low-rank matrix recovery. Thus, combined with T. Cai and A. Zhang's work, a complete characterization for sharp RIP constants delta(tk) for all t > 0 is obtained to guarantee the exact recovery of all k-sparse signals and matrices with rank at most k by l(1)-norm minimization and nuclear norm minimization, respectively. Noisy cases and approximately sparse cases are also considered. To solve the conjecture, we construct a few identities so that RIP of order tk, which is the target of our main results, can be perfectly applied to them.

• 出版日期2018-3
• 单位浙江大学