Sparse Recovery Using Quantum Annealing - Final Report

The main optimization problem in many applications in signal processing (e.g. in image reconstruction, MRI, seismic images, etc.) and statistics (e.g. model selection in regression methods), is the following sparse optimization problem. The goal is finding a sparse solution to the underdetermined linear system Ax = b, where A is an m x n matrix and b is an m-vector and m ≤ n [2]. The problem can be written as

min (over x) ||x||₁ subject to Ax = b.

There are several approaches to this problem that generally aim at approximate solutions, and often solve a simplified version of the original problem. For example passing from ℓ-norm to ℓ₁-norm yields an interesting convexification of the problem [1]. Moreover the equality Ax = b does not cover noisy cases in which Ax + r = b for some noise vector r

min (over x) ||x||₁ subject to ||Ax - b||₂ ≤ σ.

Extensive theoretical [6, 7] and practical studies [5, 8] have been carried on solving this problem and various succesfull methods adopting interior-point algorithms, gradient projections, etc. have been tested. The discrete nature of the original problem also suggests possibility of viewing the problem as a mixed-integer optimization problem [3]. However common methods for solving such mixed-integer optimization problems (e.g. Benders’ decomposition) iteratively generate hard binary optimization subproblems [4]. The exciting possibility that quantum computers may be able to perform certain computations faster than digital computers has recently spiked with the quantum hardware of D-Wave systems. The current implementations of quantum systems based on the principles of quantum adiabatic evolution, provide experimental resources for studying algorithms that reduce computationally hard problems to those that are native to the specific evolution carried by the system. In this project we will explore possibilities of designing optimization algorithms that use the power of quantum annealing in solving sparse recovery problems.

References
[1] Emmanuel J. Cand´es, Justin K. Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8):1207–1223, 2006.
[2] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkh¨user Basel, 2013.
[3] N.B. Karahanoglu, H. Erdogan, and S.I. Birbil. A mixed integer linear programming formulation for the sparse recovery problem in compressed sensing. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pages 5870–5874, May 2013.
[4] Duan Li and Xiaoling Sun. Nonlinear Integer Programming. International Series in Operations Research & Management Science. Springer, 2006.
[5] Ewout van den Berg and Michael P. Friedlander. SPGL1: A solver for large-scale sparse reconstruction, June 2007. http://www.cs.ubc.ca/labs/scl/spgl1.
[6] Ewout van den Berg and Michael P. Friedlander. Probing the pareto frontier for basis pursuit solutions. SIAM Journal on Scientific Computing, 31(2):890–912, 2008.
[7] Ewout van den Berg and Michael P. Friedlander. Sparse optimization with least-squares constraints. SIAM J. Optimization, 21(4):1201–1229, 2011.
[8] Ewout van den Berg, Michael P. Friedlander, Gilles Hennenfent, Felix J. Herrmann, Rayan Saab, and ¨Ozg¨ur Yilmaz. Algorithm 890: Sparco: A testing framework for sparse reconstruction. ACM Trans. Math. Softw., 35(4):29:1–29:16, February 2009.