Shen, JinglaiMousavi, Seyedahmad2018-11-072018-11-072018-09-27Jinglai 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/17M1140066https://doi.org/10.1137/17M1140066http://hdl.handle.net/11603/11901Motivated 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.31 pagesen-USThis 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.sparse optimizationlp-optimizationconvex optimizationnonlinear programText