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? – Marcus Müller Jul 16 '16 at 22:27
• @MarcusMüller No I am not. Please check my edit. – Undertherainbow Jul 17 '16 at 6:16
• @MarcusMüller Check the edit please. – Undertherainbow Jul 17 '16 at 7:57
• @MarcusMüller sorry for the typos, it's fixed now – Undertherainbow Jul 17 '16 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) – Marcus Müller Jul 17 '16 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. – MimSaad Jul 30 '16 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. – mark leeds Dec 23 '17 at 8:00
• Below is a reference in case it is relevant. gautampendse.com/software/lasso/webpage/pendseLassoShooting.pdf – mark leeds Dec 23 '17 at 8:04
• The question is about ${L}_{0}$ norm (Not really a norm). You try solving ${L}_{1}$ norm, why? – David Aug 19 '18 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" – MimSaad Aug 20 '18 at 18:22