Optimization Online


Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

Tristan Gally(gally***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: 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.

Keywords: compressed sensing, restricted isometry property, mixed-integer semidefinite programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )


Download: [PDF]

Entry Submitted: 04/05/2016
Entry Accepted: 04/05/2016
Entry Last Modified: 04/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society