Local and global optimality of LP minimization for sparse recovery

Laming Chen; Yuantao Gu

ICASSP 2015accepted0 citations

Local and global optimality of LP minimization for sparse recovery

Abstract

In solving the problem of sparse recovery, non-convex techniques have been paid much more attention than ever before, among which the most widely used one is ℓ p minimization with p ∈ (0, 1). It has been shown that the global optimality of ℓ p minimization is guaranteed under weaker conditions than convex ℓ 1 minimization, but little interest is shown in the local optimality, which is also significant since practical non-convex approaches can only get local optimums. In this work, we derive a tight condition in guaranteeing the local optimality of ℓ p minimization. For practical purposes, we study the performance of an approximated version of ℓ p minimization, and show that its global optimality is equivalent to that of ℓ p minimization when the penalty approaches the ℓ p “norm”. Simulations are implemented to show the recovery performance of the approximated optimization in sparse recovery.

BibTeX

@inproceedings{icassp2015_localandglobalop,
  title = {Local and global optimality of LP minimization for sparse recovery},
  author = {Laming Chen and Yuantao Gu},
  booktitle = {ICASSP 2015},
  year = {2015}
}