Nuclear norm
minimization and the affine rank minimization problem
Brian Borchers (New Mexico Tech)
ABSTRACT:
In the affine rank minimization problem, we want to find a matrix X of
minimum rank that satisfies a linear matrix equation AX=B. In
general, this is a very hard problem, since the rank of X is a
nonconvex function of X. The nuclear norm of a matrix X is the
sum of the singular values of X. The nuclear norm is a convex
function of X, and efficient algorithms exist for the minimization of
the nuclear norm of X subject to linear constraints on the elements of
X. It is surprising that in many cases it is possible to recover
a minimum rank solution to AX=B by minimizing the nuclear norm of X
subject to the linear constraints. This talk will introduce the
affine rank minimization problem, its applications, and the nuclear
norm minimization approach to solving the affine rank minimization
problem.
|