# $0$-“norm” minimization with least-squares regularization

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) 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$$.

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

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