1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Nov 2, 2016 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
    Commented Nov 2, 2016 at 22:27

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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