Finding convex conjugate of a bounded function

The convex conjugate of a function $f:\mathcal{X}\mapsto \mathbb{R}$ is formally defined as $$f^\star\left(y\right)=\sup_{x\in\mathcal{X}}\ \left\langle x,y\right\rangle-f\left(x\right).$$

In cases where $f\left(\cdot\right)$ is bounded, the supremum can become unbounded (e.g., $\mathcal{X}=\mathbb{R}^n$). To avoid this problem, $x$ is further constrained to a bounded set as I've read in textbooks and papers.

My question is that if there's a principle on how to bound $x$, because different constraints result in different convex conjugate functions. For instance, to find convex conjugate of $f\left(x\right)=\left\Vert x\right\Vert_0=\sum_{i=1}^n 1(x_i\neq 0)$ with $\mathcal{X}=\mathbb{R}^n$, it does make a difference to choose $\left\Vert x\right\Vert_{+\infty}\leq 1$ or $\left\Vert x\right\Vert_2 \leq 1$ as the bounding constraint.

-
Following Rockafellar, you can let $g$ be the function that agrees with $f$ on $\operatorname{ri}( \operatorname{dom} f)$, and $+\infty$ elsewhere. Then $f^* = g^*$ where $f^*$ is as above, and $g^*$ is taken as the $\sup$ over $\mathbb{R}^n$. Choosing different $X$ is tantamount to changing $f$. Given this, I would imagine that it would be hard to find a general principle for selecting $X$ that is independent of your application? – copper.hat May 21 '13 at 18:41
I'm curious which "textbooks and papers" you are talking about. I am unaware of any general principle for restricting $\mathcal X$ just to make sure that the supremum is bounded. On the contrary, the values of $y$ for which the supremum is unbounded is very useful information that should not be discarded without cause. – Michael Grant May 21 '13 at 19:07
@MichaelC.Grant : I didn't mean they explicitly mention bounding the constraint set is necessary, but they apply bounds in certain problems without any explanation. In addition to the example about the $\ell_0$-norm I gave in the question, convex conjugate of the rank is obtained under the bounding condition that the spectral norm is not greater than one. You can find these examples in sparse signal estimation and low-rank matrix estimation literature (e.g., see Chapter 5 of this thesis, particularly Theorem 1) – S.B. May 21 '13 at 20:25
I know that thesis, actually. You should definitely not attempt to draw any general principles about bounding the domains from Theorem 1 or from the $\ell_0$ case. Keep in mind that in both cases, the purpose is to provide a justification for the use of the nuclear norm or the $\ell_1$ norm as a convex proxy for rank or cardinality. The convex conjugate isn't even the central issue: the goal is to construct a convex envelope, which is computed using the conjugate of the conjugate. – Michael Grant May 21 '13 at 20:56
@MichaelC.Grant : I can understand the motivation, but as I commented for Laura Balzano below, the goal should be to find the best envelope rather than just an envelope. I presume taking convex conjugate of convex conjugate is a principled way to find the "tightest" convex envelope for many functions. Basically, I would like to know the method of finding the best convex envelope for all functions. – S.B. May 21 '13 at 21:07

Now that I understand the context better I am going to promote my own comments to an answer.

There is no general principle for artificially restricting the domain of a function when computing its convex conjugate. In fact, you should not do so unless you have a compelling and mathematically sound reason in your specific application. The domain of the conjugate function---that is, the set of $y$ for which the supremum is finite---is an important part of the conjugate itself, and should not be discarded. For example, when computing the dual of a convex optimization problem with an objective $f(x)$, the domain information imposes implicit constraints on the dual variables. If you remove that information, the dual problem is incorrect; it no longer provides bounds for the primal problem.

So what's going on in Chapter 5 of Ms. Fazel's thesis, or in the case of the so-called $\ell_0$ norm? Note that the interest is not in the conjugate of these functions, but rather in their convex envelopes. It just so happens that the convex envelope of a function can computed using the conjugate of the conjugate. Unfortunately, the convex envelopes of $f(x)=\mathop{\textbf{card}}(x)$ or $g(X)=\mathop{\textbf{rank}}(X)$ are not very interesting---in fact, I think they are identically zero. On other hand, the modified, extended-valued functions $$\bar{f}(x) = \begin{cases} \mathop{\textbf{card}}(x) & \|x\|_\infty \leq 1 \\ +\infty &\|x\|_\infty > 1 \end{cases}, \qquad \bar{g}(X) = \begin{cases} \mathop{\textbf{rank}}(x) & \|X\|_2 \leq 1 \\ +\infty &\|X\|_2 > 1 \end{cases}$$ have non-trivial convex envelopes.

As for why one would want these convex envelopes, it is because they provide some theoretical justification for why $\bar{f}^{**}(x)=\|x\|_1$ and $\bar{g}^{**}(X)=\|X\|_*$ are effective convex proxies for their non-convex counterparts. As you know, Ms. Fazel's thesis is entitled Matrix Rank Minimization with Applications, and it makes heavy use of trace minimization and nuclear norm minimization to find low-rank matrices that satisfy the modeling conditions. Section 5.1 is devoted to providing justifications for the convex heuristics that she uses throughout the work.

Added to clarify: you have expressed an interest in a comment above in finding the "tightest" convex envelope of a function. It's very important to note that if you truly want the tightest convex envelope for the entire function, you cannot restrict the domain in any way before taking the double conjugate. When you impose a domain restriction, you are computing the convex envelope of a different function. It will no longer serve as a lower bound for the original function. It will, however, be a tighter envelope over the domain you have selected.

You can see this for yourself: look at $f(x)=\mathop{\textbf{card}}(x)$ and $g(x)=\|x\|_1$. Clearly, there are values of $x$ for which $f(x)<g(x)$. So $g$ cannot be the convex envelope for $f$. It is, however, the convex envelope if you restrict the domain of $f$ to $\{x\,|\,\|x\|_\infty \leq 1\}$ (as we did with $\bar{f}$ above).

-
Thanks for clarifying your comment. I can understand that the restricted functions $\overline{f}$ and $\overline{g}$ produce simple enough convex envelopes. However, I'm still not convinced of why for instance we should not use the $\ell_2$ norm in $\overline{f}$ to bound the length. By the way, I think the constraint for $\overline{g}$ should be in terms of the spectral-norm of $X$ rather than $\ell_s$-norm of $X$ (maybe your notation is different from what I'm used to, though). – S.B. May 21 '13 at 21:19
Yes, by $\|X\|_2$ I am referring to the spectral norm. It is the induced matrix norm. You're probably thinking of $\|X\|_F$, the Frobenius norm. I've added some clarifications about convex envelopes above. – Michael Grant May 21 '13 at 21:22
Oops, some mistakes in my clarification. Fixed now. – Michael Grant May 21 '13 at 21:38
Since I didn't get any better answer, I'll accept yours. – S.B. Jun 21 '13 at 3:39

The trick is to find a set/constraint that is necessary and sufficient for the supremum to be finite. You mentioned Fazel's thesis; look on p58 in her proof of Theorem 1 that you are pointing out. She shows that for $\|Z\|>1$, we can choose $Y$ such that $\phi^{**}(Z)\to\infty$. On the other hand, for $\|Z\|\leq 1$, $\phi^{**}(Z) = \|Z\|_*$, which is always finite.

There is no general method here, other than to manipulate $\phi^{**}(Z)$ to see what such condition is necessary and sufficient for the supremum to be finite.

-
Thanks for pointing this out. However, my question was not why there is a need to use a bounded domain. Rather, I would like to know why we choose one form of bounding instead of another. For example, if you use $\ell_2$-norm (Frobenious norm) instead of $\ell_\infty$ (spectral norm) you end up with a totally different convex envelope for $\ell_0$ (rank). I understand that one of them give us a simpler convex envelope, but I think we should look for the best convex envelope. – S.B. May 21 '13 at 21:00