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 \Vert\cdot\Vert_*  (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 \Vert \mathbf{Z}\Vert_*, \quad\text{subj.}\quad \mathbf{XZ}=\mathbf{X}

is exactly equivalent to

\min \Vert\mathbf{Z}\Vert_*, \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.

Tagged , ,

2 thoughts on “Discovering a beautiful thing

  1. […] ICDM 2010 submission was rejected days ago, with one reviewer saying that (kind of) “the paper has nothing to do […]

  2. […] investigation into the low rank representation for subspace segmentation (ref. my earlier post here and this paper) has boiled down to understand this […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: