3
$\begingroup$

I have an optimization variable denoted as ${\bf A\in\mathbb{C}^{100\times 5}}=[{\bf a}_1\hspace{1mm} {\bf a}_2 \hspace{1mm} {\bf a}_3 \hspace{1mm} {\bf a}_4 \hspace{1mm} {\bf a}_5];$

Here, ${\bf a}_1$ is the 1st column of matrix ${\bf A}$, ${\bf a}_2$ is the 2nd column of matrix ${\bf A}$ and so on.

Let ${\bf b}=[||{\bf a}_1||_2 \hspace{1mm}||{\bf a}_2||_2 \hspace{1mm} ||{\bf a}_3||_2 \hspace{1mm} ||{\bf a}_4||_2 \hspace{1mm} ||{\bf a}_5||_2]$ be the vector of norms of all the column vectors in matrix ${\bf A}$.

In case it is beneficial we may also allow ${\bf b}=[||{\bf a}_1||_1 \hspace{1mm}||{\bf a}_2||_1 \hspace{1mm} ||{\bf a}_3||_1 \hspace{1mm} ||{\bf a}_4||_1 \hspace{1mm} ||{\bf a}_5||_1]$, i.e, L1 norm instead of L2 norm.

$\textbf{I want to make the norms zero for as many columns as possible.}$

My objective function is expressed as

$\min\hspace{3mm} ||{\bf b}||_0$

Here, $||\cdot||_2$ is L2 norm operator and $||\cdot||_0$ is L0 norm operator.

Here, norm L0 is defined as the number of nonzero elements.

We know that L0 norm is non convex. How to deal this objective? I mean linearization/convexification or approximation.

Or any other means to achieve the same.

Improve this question
$\endgroup$
7
  • $\begingroup$ First, is $\mathbf{b}$ a complex vector? Second, which $L_0$ norm do you mean? Some people (including me) use it to mean the maximum magnitude of any element in the vector. Other people (particularly in machine learning?) use it to mean the number of nonzero elements in the vector. $\endgroup$
    – prubin ♦
    Jan 18 at 20:22
  • $\begingroup$ @prubin In my case it is the number of non-zeros elements $\endgroup$
    – KGM
    Jan 18 at 20:25
  • $\begingroup$ @prubin The infinity norm is the maximum magnitude of any element in the vector. So named because it is the limit of $l _p$ norm as as $p \rightarrow \infty$. I'm a big fan of the infinity norm,, and frequently use it. I have never seen $l_0$ used to mean anything other than number of non-zeros in vector. $\endgroup$
    – Mark L. Stone
    Jan 18 at 20:42
  • $\begingroup$ To help you find relevant material for other cases not addressed in your question or @prubins' answer, the combination of norms (or pseudo -norms) is called mixed norm. For instance, $l_{2,0}$ in your case. There are some some examples of mixed norms, such as $l_{2,1}$ in the CVX forum. $\endgroup$
    – Mark L. Stone
    Jan 18 at 20:47
  • $\begingroup$ @MarkL.Stone I'm aware of the $L_\infty$ norm and agree that's the proper name. I can't recall where I've seen $L_0$ used as a "synonym" for $L_\infty,$ but I know I have, and I'm pretty sure I've done it myself at some point in the past (which does not even make my personal list of top 10 mathematical sins). $\endgroup$
    – prubin ♦
    Jan 18 at 23:20

1 Answer 1

Reset to default
3
$\begingroup$

You can introduce binary variables $\mathbf{z}\in \lbrace 0, 1 \rbrace^n$ (where $n$ is the dimension of $\mathbf{b}$) together with the constraints $b_i \le M_i z_i,$ where $M_i$ is an upper bound for $\vert b_i \vert,$ and then minimize $\sum_i z_i.$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. Does it make any difference if $b_i=||{\bf a}_i||_1$ instead? $\endgroup$
    – KGM
    Jan 18 at 21:16
  • $\begingroup$ You can change the constraints to $\vert a_{j,i} \vert \le M_{j,i} z_i \quad \forall j,i,$ where $M_{j,i}$ is an upper bound for $\vert a_{j,i} \vert.$ That sets $z_i=1$ if any component of $\mathbf{a}_i$ is nonzero. $\endgroup$
    – prubin ♦
    Jan 18 at 23:25
  • $\begingroup$ why is the question of $b_i$ being real or complex? $b_i=||{\bf a}_i||_2$ where ${\bf a}_i$ is a vector of complex elements. Since $b_i$ is a norm, $b_i$ is positive and real, right? $\endgroup$
    – KGM
    Jan 19 at 10:26
  • $\begingroup$ Good point. I think I missed something in the question. I have simplified my answer based on $b_i$ being a (nonnegative real) norm value. $\endgroup$
    – prubin ♦
    Jan 19 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.