Discovering a Beautiful Thing

Recent several months I have turned my attention to low-rank minimization and related techniques, among other lines. In general, minimizing the rank of a matrix is NP-hard, due to its combinatorial nature. Recently, there is much research effort to use nuclear norm $\|\cdot\|_*$  (sum of singular values) as a surrogate for rank, pioneered by this Ph.D thesis. And this turns out to be an extremely powerful mathematical tool that has enabled the recent successful research endeavors on low-rank matrix completion led by Emmanuel Candes, and many others. The most wonderful part with nuclear norm minimization is that nuclear norm is a convex function, and hence a global minimizer can always be expected.

Investigating a problem in a different context, we have managed to prove that

$\min \| \mathbf{Z}\|_*, \quad \text{subj.} \quad \mathbf{XZ}=\mathbf{X}$

is exactly equivalent to

$\min \|\mathbf{Z}\|*, \quad\text{subj.}\quad \mathbf{XZ}=\mathbf{X}, \mathbf{Z}\succeq \mathbf{0}$.

And both have unique minimizers. The beautiful thing included is that: solving the first problem will always return a unique minimizer which is symmetric positive semidefinite, which is hard to see from the problem itself.

Since the manuscript was submitted for anonymous review, I’ll not disclose too much information here but will follow up later.