Least Sparsity of p-Norm Based Optimization Problems with p>1*
Loading...
Links to Files
Author/Creator
Author/Creator ORCID
Date
2018-09-27
Type of Work
Department
Program
Citation of Original Publication
Jinglai Shen and Seyedahmad Mousavi, Least Sparsity of p-Norm Based Optimization Problems with p>1*, SIAM Journal on Optimization ,Volume 28, Issue 3, DOI: 10.1137/17M1140066
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
©2018 SIAM No commerical use allowed.
©2018 SIAM No commerical use allowed.
Abstract
Motivated by lp-optimization arising from sparse optimization, high-dimensional data analytics and statistics, this paper studies sparse properties of a wide range of p-norm based optimization problems with p > 1, including generalized basis pursuit, basis pursuit denoising, ridge regression, and elastic net. It is well known that when p > 1, these optimization problems lead to less
sparse solutions. However, the quantitative characterization of the adverse sparse properties is not available. This paper shows how to exploit optimization and matrix analysis techniques to develop a systematic treatment of a broad class of p-norm based optimization problems for a general p > 1 and show that their optimal solutions attain full support, and thus have the least sparsity, for almost all measurement matrices and measurement vectors. Comparison to lp-optimization with 0 < p <=1 and implications for robustness as well as extensions to the complex setting are also given. These results shed light on analysis and computation of general p-norm based optimization problems in various applications.