An Efficient Method for Convex Constrained Rank Minimization Problems Based on DC Programming

The constrained rank minimization problem has various applications in many fields including machine learning, control, and signal processing. In this paper, we consider the convex constrained rank minimization problem. By introducing a new variable and penalizing an equality constraint to objective...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical problems in engineering 2016-01, Vol.2016 (2016), p.1-13
Main Authors: Yang, Wanping, Xu, Fengmin, Zhao, Jinkai
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Closed form solutions
Constraints
Data compression
Data processing
Lower bounds
Machine learning
Mathematical analysis
Mathematical models
Mathematical problems
Methods
Minimization
Optimization
Programming
Recoverability
Semidefinite programming
Signal processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The constrained rank minimization problem has various applications in many fields including machine learning, control, and signal processing. In this paper, we consider the convex constrained rank minimization problem. By introducing a new variable and penalizing an equality constraint to objective function, we reformulate the convex objective function with a rank constraint as a difference of convex functions based on the closed-form solutions, which can be reformulated as DC programming. A stepwise linear approximative algorithm is provided for solving the reformulated model. The performance of our method is tested by applying it to affine rank minimization problems and max-cut problems. Numerical results demonstrate that the method is effective and of high recoverability and results on max-cut show that the method is feasible, which provides better lower bounds and lower rank solutions compared with improved approximation algorithm using semidefinite programming, and they are close to the results of the latest researches.
ISSN:1024-123X
1563-5147
DOI:10.1155/2016/7473041