Local and global optimality of LP minimization for sparse recovery
Lists
Only you see this
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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> minimization with p ∈ (0, 1). It has been shown that the global optimality of ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> minimization is guaranteed under weaker conditions than convex ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> 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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> minimization. For practical purposes, we study the performance of an approximated version of ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> minimization, and show that its global optimality is equivalent to that of ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> minimization when the penalty approaches the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> “norm”. Simulations are implemented to show the recovery performance of the approximated optimization in sparse recovery.
BibTeX
@inproceedings{chen2015local,
author = {Laming Chen and Yuantao Gu},
title = {{Local and global optimality of LP minimization for sparse recovery}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2015},
doi = {10.1109/icassp.2015.7178641},
}Loading related content...