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 &amp; {\left\| x \right\|}_{0} \\
\text{subject to} \quad &amp; f \left( x \right) \leq d \\
&amp; 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 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&lt;=150; % f(x) here, is x^2
      0&lt;=x&lt;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/