Decomposition in Transition: Adaptive Matrix Factorization - Realtime Data Mining - page 172

Why is the transition to formulation ( 8.31 ) so important? Whereas the rank
function in ( 8.30 ) counts the number of nonvanishing singular values, the nuclear
norm sums their amplitude and, in some sense, is to the rank functional what the
convex l 1 norm is to the counting l 0 norm in the area of sparse signal recovery. The
main point here is that the nuclear norm is a convex function and can be optimized
efficiently via semidefinite programming.
When the matrix variable X is symmetric and positive semidefinite, the nuclear
norm of X is the sum of the (nonnegative) eigenvalues and thus equal to the trace of
X . Hence, for positive semidefinite unknown, ( 8.31 ) would simply minimize the
trace over the constraint set

trace ðÞ

minimize

subject to P Ω ðÞ¼P Ω A
X 0

,

which is a semidefinite program. Recall that an n n matrix A is called positive
semidefinite , denoted by A 0, if

x T Ax 0

for all vectors x of length n . For an introduction to semidefinite programming, see,
e.g., [VB96].
For a general matrix A which may be not positive semidefinite and even not
symmetric, the nuclear norm heuristic ( 8.31 ) can be formulated in terms of
semidefinite programming as being equivalent to

1
2

minimize ð trace WðÞþ trace WðÞ Þ

P Ω ðÞ¼P Ω A
W 1 X
X T

ð 8 : 34 Þ

subject to

0

W 2

with additional optimization variables W 1 and W 2 . To outline the analogy
(strongly simplified; for details, see [RFP10]), we consider the singular value
decomposition of X

X ¼ USV T

and of the block matrix

S U T

W 1 X
X T

U
V

¼

V T

W 2

leading to W 1 ¼ USU T and W 2 ¼ VSV T . Since the left and right singular vector
matrices are unitary, the traces of W 1 and W 2 are equal to the nuclear norm of X .