I am interested in the optimization problem known as "analysis regularization":

$$ {\rm argmin}_{x \in \mathbb{R}^{p}}\frac{1}{2}\|y - Ax\|_2^2 + \lambda \|D^T x\|_1,$$ where $y \in \mathbb{R}^n$, $A \in \mathbb{R}^{n \times p}$, and $D \in \mathbb{R}^{p \times d}$. In this paper, they state that the set of (global) minimizers to the above is nonempty and compact if and only if $$ {\rm kern}(A) \cap {\rm kern}(D^T) = 0.$$

How would one be able to prove this? They claim it to be a classic result, but I am not able to show it myself after a few attempts. I am unfamiliar with this area, so I may be overlooking a simpler argument.

Any references or pointers to relevant material would be helpful.

  • 1
    $\begingroup$ It's a convex and continuous functional, so the only thing missing to show existence of a minimizer is boundedness: you need to argue that the minimizer -- if it exists -- must lie in a bounded subset of $\mathbb{R}^p$. For that, it suffices to show that if $\|x\|\to\infty$, so must the functional value. But the condition you give implies that in this case either the first or the second term must explode. (The actual proof is a bit -- but not much -- more complicated, since $x$ need not lie purely in one null space or the other.) $\endgroup$ – Christian Clason Nov 2 '16 at 19:31
  • $\begingroup$ Just in case it wasn't clear: If you've shown that, then the problem is equivalent to minimizing a continuous function over a bounded and closed set, which (in a finite dimensional normed vector space) attains its minimum by Weierstrass's theorem. $\endgroup$ – Christian Clason Nov 2 '16 at 22:27

Nothing is stated concerning $\lambda$. I will assume that (as always) the regularization parameter $\lambda >0$. Otherwise the whole thing does not really make sense.

The expression to be minimized is a convex function in $x$, so the set of minimizers is convex. Also every local minimizer is a global minimizer.

If the intersection of the kernels is empty, then it is not too hard to show that $$ \lim_{r\to\infty} \left( \min_{\|x\|_2 = r} \left\{\frac{1}{2}\|y-Ax\|_2 + \lambda\|D^Tx\|_1\right\}\right) = +\infty . \tag{*}$$ Assume this is not the case. Then choose a sequence $x_k\to \infty$, so that the function stays bounded on that sequence. Then $x_k/\|x_k\|$ may be assumed to converge, say to $x^*$. Then $D^T x^*=0$. But then $x^*$ is not in the kernel of $A$ and this gives a contradiction. Now (*) implies that the set of minimizers is nonempty and compact.

If the kernels intersect, then we can first consider the problem on a complementary subspace to the intersection of the kernels. By the previous argument this restricted problem has a minimizer. If you have a minimizer $\bar x$ and there are points $z$ such that $Az=D^Tz=0$, then of course $\bar x + \alpha z$ is a minimizer for any $\alpha \in \mathbb{R}$. So if the kernels have nontrivial intersection the set of minimizers is not compact.


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.