A Non-Convex Relaxation for Fixed-Rank Approximation

2017/06/19 by Olsson, Carl, Carlsson, Marcus, Bylow, Erik
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1706.05855

Abstract

This paper considers the problem of finding a low rank matrix from observations of linear combinations of its elements. It is well known that if the problem fulfills a restricted isometry property (RIP), convex relaxations using the nuclear norm typically work well and come with theoretical performance guarantees. On the other hand these formulations suffer from a shrinking bias that can severely degrade the solution in the presence of noise. In this theoretical paper we study an alternative non-convex relaxation that in contrast to the nuclear norm does not penalize the leading singular values and thereby avoids this bias. We show that despite its non-convexity the proposed formulation will in many cases have a single local minimizer if a RIP holds. Our numerical tests show that our approach typically converges to a better solution than nuclear norm based alternatives even in cases when the RIP does not hold.

Related

• Non-Convex Rank/Sparsity Regularization and Local Minima
• Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
• A convex relaxation to compute the nearest structured rank deficient\n matrix
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• An unbiased approach to low rank recovery