1

Here's a simple constrained optimization problem ($X,P \in\mathbb{R}^{m\times n}$):

$Minimize_{X}~ \|P-X\|_{F}^{2}$

$subject~to~\|X\|_{0}= k$.

The optimal $X$ can be got by setting all but the $k$ largest elements of $P$ to zero. That seems intuitive enough, since the lowest the objective can be is zero (when $X=P$), and because of the constraint, we only keep k non-zero elements. How can I prove this analytically?

In a similar vein, how do I analytically find the minimizer to the following problem ($D\in\mathbb{R}^{n\times n}$)?

$Minimize_{X}~ \|P-X\|_{F}^{2}+\gamma\|DX\|_{1}$

$subject~to~\|X\|_{0}= k$.

Can I do the following: find an $X$ that minimizes the objective (introduce a splitting variable and use Augmented Lagrangian) and then keep only the $k$ largest components? Is there a better way?

nemo
  • 638
  • What does $|\cdot|_0$ mean? – copper.hat Mar 03 '15 at 17:04
  • Assuming that it means the number of non-zero elements, if you take $k=1$ with $m=n=1$, then letting $P=0$ shows that there is no optimal $X$ (it can be arbitrarily small, but never zero). – copper.hat Mar 03 '15 at 17:09
  • Yes, it means the number of non-zero elements. P is a non-zero matrix, m is of the order of a few thousands, n a few hundreds and k is much less than mn (but a few hundreds in most cases). – nemo Mar 03 '15 at 17:25
  • How to solve the second problem then? – nemo Mar 03 '15 at 17:47

0 Answers0