1
$\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$
  • 1
    $\begingroup$ And what is $\|x\|_0$? $\endgroup$ – fedja Jul 13 at 1:20
  • $\begingroup$ zero-norm measuring the number of non-zero elements in $\mathbf{x}$ $\endgroup$ – Michael Fan Zhang Jul 13 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$ – Michael Fan Zhang Jul 13 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$ – Rodrigo de Azevedo 17 hours ago
0
$\begingroup$

$\ell_0$ optimization is NP hard in general, even strongly so: https://web.stanford.edu/~yyye/lpmin_v14.pdf

$\endgroup$
  • $\begingroup$ This one probably has good approximation. $\endgroup$ – VS. Jul 13 at 22:11
  • $\begingroup$ thanks, i will take a look. $\endgroup$ – Michael Fan Zhang 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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