Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the key conditions in this context. However, computing the best constants for this condition is itself NP-hard. In this paper we propose a mixed-integer semidefinite programming approach for computing these optimal constants. This also subsumes sparse principal component analysis. Computational results with this approach allow to evaluate earlier semidefinite relaxations and show that the quality that can be obtained in reasonable time is limited.

Article

Download

View Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming