/
nuclearnorm.jl
57 lines (48 loc) · 1.64 KB
/
nuclearnorm.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#############################################################################
# nuclearnorm.jl
# Handles nuclear norm (the sum of the singular values of a matrix),
# All expressions and atoms are subtypes of AbstractExpr.
# Please read expressions.jl first.
#############################################################################
### Nuclear norm
struct NuclearNormAtom <: AbstractExpr
head::Symbol
id_hash::UInt64
children::Tuple{AbstractExpr}
size::Tuple{Int, Int}
function NuclearNormAtom(x::AbstractExpr)
children = (x,)
return new(:nuclearnorm, hash(children), children, (1,1))
end
end
function sign(x::NuclearNormAtom)
return Positive()
end
# The monotonicity
function monotonicity(x::NuclearNormAtom)
return (NoMonotonicity(),)
end
function curvature(x::NuclearNormAtom)
return ConvexVexity()
end
function evaluate(x::NuclearNormAtom)
return sum(svdvals(evaluate(x.children[1])))
end
nuclearnorm(x::AbstractExpr) = NuclearNormAtom(x)
# Create the equivalent conic problem:
# minimize (tr(U) + tr(V))/2
# subject to
# [U A; A' V] ⪰ 0
# see eg Recht, Fazel, Parillo 2008 "Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization"
# http://arxiv.org/pdf/0706.4138v1.pdf
function conic_form!(x::NuclearNormAtom, unique_conic_forms)
if !has_conic_form(unique_conic_forms, x)
A = x.children[1]
m, n = size(A)
U = Variable(m,m)
V = Variable(n,n)
p = minimize(.5*(tr(U) + tr(V)), [U A; A' V] ⪰ 0)
cache_conic_form!(unique_conic_forms, x, p)
end
return get_conic_form(unique_conic_forms, x)
end