CS: A Checkable Necessary and Sufficient Condition for Testing Measurement Matrices ?

If you have been reading this blog for a little while, you know that there are reasons to be dissatisfied with the current state of affairs with our testing of the restricted isometry property (RIP) given a certain measurement matrix. I believe this is central to unleashing some major hardware implementation. Take for instance Roummel Marcia and Rebecca Willett's coded aperture architecture in Compressive Coded Aperture Superresolution Image Reconstruction (additional material can be found here while the slides are here). Much of the work in this paper goes into fitting a Toeplitz-like configuration on the mask so that it eventually fulfills the RIP condition. As we also know there are problems with the RIP itself in that it just a sufficient condition. And so one wonders if a checkable necessary and sufficient condition on the measurement matrix would simplify this problematic and enable more versatile applications.

If you recall, in a previous entry, a paper by Weiyu Xu, Babak Hassibi entitled Compressed sensing over the Grassmann manifold: A unified analytical framework provided a necessary and sufficient condition for solving the L1 problem with a matrix A that followed a certain null-space property. I was intrigued by that property and went ahead and asked the authors whether they knew "of an algorithm that is not NP-hard and that would allow that property [property (4) of theorem 1] to be tested given a certain matrix ?" I also added that I was sure that they knew about Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui and wondered if a similar approach could be used.

One of the authors, Weiyu Xu, kindly responded and allowed me to post his response:

...How to test the discussed property using a non-exponential complexity algorithm is not discussed in our paper yet. Currently we do not know any polynomial-time algorithm for testing it. The paper by d'Aspremont etc. is very interesting and can possibly be used to test this null-space property....

As featured earlier, Yin Zhang devised a necessary and sufficient property bypassing RIP in On theory of compressive sensing via ell-1-minimization: Simple derivations and extensions. So I went ahead and naively asked him:

.. can you confirm to me that you know of no non-NP-Hard algorithm that given a measurement matrix A, would verify theorem 2 (i.e. find a standard normal B such that BA^T = 0 ) or proposition 2 of your paper.

Yin kindly responded

Yes, I don't think proposition 2 can be verified in polynomial time. The bound in Theorem 2 is probabilistic, and I don't think it can be verified deterministically for a given matrix in poly time either. So I agree with you.

So it looks like an answer to this post's title is: No and as we say in Texas, it's not just a shame, it's a damn shame.


Credit: NASA/JPL-Caltech/University of Arizona/Texas A&M, clouds on Mars as seen from Phoenix on sol 98.