# Approximating ${L}_{0}$ Norm Minimization with Non Linear Convex Inequality Constraints using Reweighted ${L}_{1}$ Minimization

I have an optimization problem consisting of the ${\ell}_{0}$ norm as the objective and a nonlinear (convex) constraint as well as a linear constraint. I am wondering if the reweighted ${\ell}_{1}$ norm minimization algorithm would be applicable to this problem. The original paper "Enhancing Sparsity by Reweighted ${\ell}_{1}$ Minimization" assumes linear constraints. References to relevant papers would be appreciated.

Edit: This is the problem:

\begin{align} \arg \min_{x} \quad & {\left\| x \right\|}_{0} \\ \text{subject to} \quad & f \left( x \right) \leq d \\ & 0 \leq {x}_{i} \leq p \end{align}

where $x \in \mathbb{R}^{n}$, $d, p \in \mathbb{R}$ are constants, and $f \left( x \right)$ is a convex function. The notation ${\left\| \cdot \right\|}_{0}$ refers to the ${\ell}_{0}$ norm, which is the number of nonzero entries the vector for which it is being computed.

I wish to relax the objective using reweighted ${\ell}_{1}$ minimization, but am wondering if the constraints must be linear for this heuristic to apply.

Also this is not compressive sensing. I just wish to make use of a technique in compressive sensing.

• I think your question would benefit from having more formulaz; can you at least add a formalized version of your nonlinear constraint? Jul 16, 2016 at 22:27
• @MarcusMüller No I am not. Please check my edit. Jul 17, 2016 at 6:16
• @MarcusMüller Check the edit please. Jul 17, 2016 at 7:57
• @MarcusMüller sorry for the typos, it's fixed now Jul 17, 2016 at 10:00
• Saying $x_i \le P$, and $P$ is the maximum value for any entry of $\mathbf x$ is totally redundant, and doesn't add info. (yes, "redundant and doesn't add info" is a play on words :D) Jul 17, 2016 at 10:22

I think testing it practically rather that its theoretical inspection might help more. Therefore, I tried to solve the above mentioned problem using CVX toolbox in Matlab.

cvx_begin;
variable x(1000);
minimise(norm(x,1));
subject to
x.^2<=150; % f(x) here, is x^2
0<=x<10;
cvx_end


I think the answer to your question depends on your function f(x), and sometimes even if there is a solution based on convexification of the stated problem, I do not see any guarantees that the answer is must be right. I mean using l1 norm as proxy for l0 norm (as what CS suggests) in this case, might be wrong and bring no fruit. Be careful with blind application of l1 norm minimization method. This great lecture from Prof. Baranuik called "Compressive nonSensing" might be help you more on this regard: You might find it here: http://www.norbertwiener.umd.edu/FFT/2015/

• As you might know, the above CVX implementation is not l1 reweighed and is regular l1 norm minimization algorithm, however I do not think it changes anything. Jul 30, 2016 at 14:30
• Just to pipe in, I'm not familar with how the re-weighting using l1-norm works but you may want to look at the lasso methodology. it probably doesn't apply directly to your problem but it is related in that it's an algorithm for finding sparse solutions to minimization problems. google hastie or tibishrani for more details. Dec 23, 2017 at 8:00
• Below is a reference in case it is relevant. gautampendse.com/software/lasso/webpage/pendseLassoShooting.pdf Dec 23, 2017 at 8:04
• The question is about ${L}_{0}$ norm (Not really a norm). You try solving ${L}_{1}$ norm, why? Aug 19, 2018 at 17:34
• The l1 norm can be used as a proxy in case the signal is sparse. Please google this paper "An Introduction To Compressive Sampling" Aug 20, 2018 at 18:22