Non-convex Compressed Sensing with the Sum-of-Squares Method

Tasuku Soma, Yuichi Yoshida

Abstract

We consider stable signal recovery in ℓq quasi-norm for 0 < q ≤ 1. In this problem, given a measurement vector y = Ax for some unknown signal vector x ∊ ℝn and a known matrix A ∊ ℝm×n, we want to recover z ∊ ℝn with ‖x – z‖q = O(‖x – x*‖q) from a measurement vector, where x* is the s-sparse vector closest to x in ℓq quasi-norm. Although a small value of q is favorable for measuring the distance to sparse vectors, previous methods for q < 1 involve ℓq quasi-norm minimization which is computationally intractable. In this paper, we overcome this issue by using the sum-of-squares method, and give the first polynomial-time stable recovery scheme for a large class of matrices A in ℓq quasi-norm for any fixed constant 0 < q ≤ 1.
BibTeX
@inproceedings{soma2016non,
  author = {Tasuku Soma and Yuichi Yoshida},
  title = {{Non-convex Compressed Sensing with the Sum-of-Squares Method}},
  booktitle = {SODA},
  year = {2016},
  doi = {10.1137/1.9781611974331.ch42},
}

Loading related content...

Figure