A Unified Approach for Minimizing Composite Norms

Details A Unified Approach for Minimizing Composite Norms A Unified Approach for Minimizing Composite Norms

2010-05-26

arxiv.org/abs/1005.4733v2

Mathematics

Optimization and Control

Scientific paper

We propose a first-order augmented Lagrangian algorithm (FALC) that solves min{mu1|X|_* + mu2 |C(X)-d|_1 : A(X)=b}, where C(.) and A(.) denote linear operators from Re^{m*n} to a vector space. FALC solves this semidefinite problem by inexactly solving a sequence of problems of the form min{lambda(k)(mu1 |X|_* + mu2 |s|_1)+|A(X)-b-lambda(k)theta1(k)|_2^2+|C(X)+s-d-lambda(k)theta2(k)|_2^2}, for an appropriately chosen sequence of multipliers {lambda(k),theta1(k),theta2(k)}. Each of these subproblems are solved using Algorithm 3 in [31] by Paul Tseng wherein each update can be computed using singular value decomposition (SVD). We show that FALC converges to the optimal solution X* of the composite norm minimization problem if the optimal solution is unique. We also show that there exists a priori fixed sequence {lambda(k)} such that for all epsilon>0, iterates X(k) computed by FALC are epsilon-feasible and epsilon-optimal after O(log(1/epsilon)) iterations, which requires O(1/epsilon) operations in total where the complexity of each operation is dominated by computing a singular value decomposition. We also show that FALC can be extended very simply to solve more general problems of the form: min{mu1 |X|_{alpha}+ mu2 |C(X)-d|_{beta} + : A(X)=b, Q-F(X) is psd, |G(X)-h|_{gamma} <= rho}, where the matrix norm |X|_{alpha} denotes either the Frobenius, the nuclear, or the L_2-operator norm, the vector norms |C(X)-d|_{beta}, and |G(X) - h|_{gamma} denote either the L2-norm, L1-norm or the L{infty}-norm, and A(X), C(X), G(X) and F(X) are linear operators from Re^{m*n} to vector spaces of appropriate dimensions and psd is the set of positive semidefinite matrices. All the convergence properties of FALC continue to hold for this more general problem.

Affiliated with

Also associated with

No associations

Rating

A Unified Approach for Minimizing Composite Norms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Unified Approach for Minimizing Composite Norms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Unified Approach for Minimizing Composite Norms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-605238