Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES

Abstract: 

Given a data matrix with partially observed entries, the low-rank matrix completion problem is one of finding a matrix with the lowest rank that perfectly fits the given observations. While there exist convex relaxations for the low-rank completion problem, the underlying problem is inherently non-convex, and most algorithms (alternating projection, Riemannian optimization, etc.) heavily depend on the initialization. This paper proposes an improved initialization that relies on successive rank-1 updates. Further, the paper proposes theoretical guarantees under which the proposed initialization is closer to the unknown optimal solution than the all zeros initialization in the Frobenius norm. To cope with the problem of local minima, the paper introduces and uses random norms to change the position of the local minima while preserving the global one. Using a Riemannian optimization routine, simulation results reveal that the proposed solution succeeds in completing Gaussian partially observed matrices with a random set of revealed entries close to the information-theoretical limits, thereby significantly improving on prior methods.

up
0 users have voted:

Paper Details

Authors:
Ahmed Douik, Babak Hassibi
Submitted On:
19 April 2018 - 3:10pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Ahmed Douik
Paper Code:
3522
Document Year:
2018
Cite

Document Files

Presentation_v2.pdf

(4 downloads)

Presentation Slides

(4 downloads)

Subscribe

[1] Ahmed Douik, Babak Hassibi, "AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES", IEEE SigPort, 2018. [Online]. Available: http://sigport.org/2921. Accessed: Apr. 21, 2018.
@article{2921-18,
url = {http://sigport.org/2921},
author = {Ahmed Douik; Babak Hassibi },
publisher = {IEEE SigPort},
title = {AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES},
year = {2018} }
TY - EJOUR
T1 - AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES
AU - Ahmed Douik; Babak Hassibi
PY - 2018
PB - IEEE SigPort
UR - http://sigport.org/2921
ER -
Ahmed Douik, Babak Hassibi. (2018). AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES. IEEE SigPort. http://sigport.org/2921
Ahmed Douik, Babak Hassibi, 2018. AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES. Available at: http://sigport.org/2921.
Ahmed Douik, Babak Hassibi. (2018). "AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES." Web.
1. Ahmed Douik, Babak Hassibi. AN IMPROVED INITIALIZATION FOR LOW-RANK MATRIX COMPLETION BASED ON RANK-1 UPDATES [Internet]. IEEE SigPort; 2018. Available from : http://sigport.org/2921