Jaya Narasimhan
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2016-79
May 13, 2016
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.pdf
In this report we lower the bounds on the number of required sampled entries for reconstructing low- rank positive semidefinite matrices through nuclear norm minimization. We show for an n × n matrix of rank r only O(r n logn loglogn) samped entries are needed to complete the matrix as compared to previous work’s O(r n log^2 n) entries. We obtain this result by using rejection sampling when constructing a dual variable certificate.
Advisor: Satish Rao
BibTeX citation:
@mastersthesis{Narasimhan:EECS-2016-79, Author = {Narasimhan, Jaya}, Title = {Low-Rank Matrix Completion for Positive Semidefinite Matrices}, School = {EECS Department, University of California, Berkeley}, Year = {2016}, Month = {May}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.html}, Number = {UCB/EECS-2016-79}, Abstract = {In this report we lower the bounds on the number of required sampled entries for reconstructing low- rank positive semidefinite matrices through nuclear norm minimization. We show for an n × n matrix of rank r only O(r n logn loglogn) samped entries are needed to complete the matrix as compared to previous work’s O(r n log^2 n) entries. We obtain this result by using rejection sampling when constructing a dual variable certificate.} }
EndNote citation:
%0 Thesis %A Narasimhan, Jaya %T Low-Rank Matrix Completion for Positive Semidefinite Matrices %I EECS Department, University of California, Berkeley %D 2016 %8 May 13 %@ UCB/EECS-2016-79 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-79.html %F Narasimhan:EECS-2016-79