2
$\begingroup$

I have the following optimization problem in $\mathbf{x} \in \mathbb{R}^{K \times 1}$

$$\min_{\mathbf{x}>0} \quad \|\mathbf{A}\mathbf{x}\|_0 + \alpha \|\mathbf{B}\mathbf{x}-\mathbf{c}\|_2^2$$

where $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{L \times K}$ are (very) fat matrices ($L<K$) and $\mathbf{c} \in \mathbb{R}^{L\times 1}$. Moreover,

$$\mathbf{A} = \left( \begin{array} {cccccccccccccccccc} \mathbf{1}_1 & \mathbf{0} & \cdots & \mathbf{0}\\ \mathbf{0} & \mathbf{1}_2 & \cdots & \mathbf{0} \\ \vdots &\vdots & \ddots&\vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{1}_K \\ \end{array} \right)$$

where $\mathbf{1}_k=(1, 1, \dots, 1)$ is a $1 \times m_k$ vector whose elements are $1$.

$\endgroup$
5
  • 2
    $\begingroup$ And what is $\|x\|_0$? $\endgroup$
    – fedja
    Commented Jul 13, 2019 at 1:20
  • $\begingroup$ zero-norm measuring the number of non-zero elements in $\mathbf{x}$ $\endgroup$ Commented Jul 13, 2019 at 5:13
  • $\begingroup$ $\mathbf{A}=\left( \begin{array} {cccccccccccccccccc} \mathbf{1}_1 & \mathbf{0} & \cdots & \mathbf{0}\\ \mathbf{0} & \mathbf{1}_2 & \cdots & \mathbf{0} \\ \vdots &\vdots & \ddots&\vdots \\ \mathbf{0} & \mathbf{0} & \cdots & \mathbf{1}_K \\ \end{array} \right)$ and $\mathbf{1}_k=(1, 1, \dots, 1)$ is a $1\times m_k$ vector with all the elements being $1$. $A^T$ is a very tall matrix. $\endgroup$ Commented Jul 13, 2019 at 13:09
  • $\begingroup$ Since matrix $\bf B$ is very fat, why even use least-squares regularization? Why not append the equality constraint $\bf Bx = c$? To me, this very much looks like a least-norm problem in the $0$-"norm". $\endgroup$ Commented Jul 16, 2019 at 18:22
  • 2
    $\begingroup$ Have you looked into compressive sensing literature, specifically lasso problem where 0 norm is replaced by one norm without changing the solution. $\endgroup$ Commented Apr 12, 2020 at 12:15

1 Answer 1

0
$\begingroup$

$\ell_0$ optimization is NP-hard in general, even strongly so:

$\endgroup$
2
  • $\begingroup$ This one probably has good approximation. $\endgroup$
    – VS.
    Commented Jul 13, 2019 at 22:11
  • $\begingroup$ thanks, i will take a look. $\endgroup$ Commented Jul 15, 2019 at 1:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .