In Fazel (2002) Matrix rank minimization with applications, Ch. 5.1.4-5.1.5, the author finds an analytic expression for the convex biconjugate of their nonconvex function; however, they state that minimizing the biconjugate only provides a lower bound on the original problem. (Specifically, that $\text{conv rank} X = \|X\|_*$)

By my understanding,

  • The biconjugate of a function is its convex hull (point-wise greatest convex envelope) $$f^{**}(x) = \mbox{conv} f(x)$$

  • The minimizer of the convex hull of a function is also the minimizer of the function itself $$\arg\min f(x) = \arg\min \mbox{conv} f(x) = \arg\min f^{**}(x)$$

If so, why does the double conjugate only provide a lower bound and not the true minimum?


Your mistake is making this claim: $$\mathop{\textrm{conv}} \mathop{\textrm{rank}} X = \|X\|_*$$ That is incorrect, and not an accurate reflection of the dissertation. This is the claim made, expressed in extended-value form: $$\phi(X) = \begin{cases} \mathop{\textrm{rank}} X & \|X\|\leq 1 \\ +\infty & \text{otherwise} \end{cases} \quad\Longrightarrow\quad \phi^{**}(X) = \|X\|_*$$ Even if you know that $\|X\|\leq 1$, this wouldn't be enough to give you a true minimum. After all, the problems you really want to solve are like this: \begin{array}{ll} \text{minimize} & \mathop{\textrm{rank}}(X) \\ \text{subject to} & X \in \mathcal{C} \end{array} where $\mathcal{C}$ is a more general convex set. To get a true minimum you need the convex envelope for this function: $$\phi(X) = \begin{cases} \mathop{\textrm{rank}} X & X \in \mathcal{C} \\ +\infty & \text{otherwise} \end{cases}$$ And the likelihood that you can compute that for any useful $\mathcal{C}$ is small.


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.