OptSpace 代码

Matrix Completion from a Few Entries OptSpace-A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion 源码

function [X S Y dist] = OptSpace（M_Ernitertol）
% An algorithm for Matrix Reconstruction from a partially revealed set. 
% See “Matrix Completion from a Few Entries“（http://arxiv.org/pdf/0901.3150） for details
% Usage :
% [X S Y dist] = OptSpace（Arnitertol）;
% [X S Y dist] = OptSpace（A）;
% 
% INPUT :
% A     :  The partially revealed matrix.
%          Sparse matrix with zeroes at the unrevealed indices.
%
% r     :  The rank to be used for reconstruction. Use [] to guess the rank.
% niter :  The max. no. of iterations. Use [] to use default （50）.
% tol   :  Stop iterations if norm（ （XSY‘ - M_E）.*E  ‘fro‘ ）/sqrt（|E|） < tol where
%        - E_{ij} = 1 if M_{ij} is revealed and zero otherwise 
%        - |E| is the size of the revealed set.				
%        - Use [] to use the default （1e-6）
%
%
% OUTPUT :
% X      : A size（A1）xr matrix
% S      : An rxr matrix
% Y      : A size（A2）xr matrix
% such that M_hat = X*S*Y‘ 
% dist   : A vector containing norm（ （XSY‘ - M_E）.*E  ‘fro‘ ）/sqrt（|E|） at each
%          successive iteration
%
% Date : 21st April 2009
% COPYRIGHT 2009 Raghunandan H. Keshavan Andrea Montanari Sewoong Oh





if（nargin==1）
	
	M_E = sparse（M_E）;
	[n m] = size（M_E）;
	E = spones（M_E）;
	eps = nnz（E）/sqrt（m*n） ;

	tol = 1e-6;

	fprintf（1‘Rank not specified. Trying to guess ...\n‘）;
	r = guessRank（M_E） ;
	fprintf（1‘Using Rank : %d\n‘r）;
	
	m0 = 10000 ;
	rho = 0;
	
	niter = 50;
elseif（nargin==4）
	
	M_E = sparse（M_E）;
	[n m] = size（M_E）;
	E = spones（M_E）;
	eps = nnz（E）/sqrt（m*n） ;

	if（ length（tol） == 0 ）
		tol = 1e-6;
	end

	if（ length（r） == 0 ）

		fprintf（1‘Rank not specified. Trying to guess ...\n‘）;
		r = guessRank（M_E） ;
		fprintf（1‘Using Rank : %d\n‘r）;
	end

	m0 = 10000 ;
	rho = 0;

	if（ length（niter） == 0 ）
		niter = 50 ;
	end	
else
	fprintf（1‘Improper arguments （See “help OptSpace“）\n‘）;
	fprintf（1‘Usage :\n[X S Y dist] = OptSpace（Arnitertol） \n‘） ;
	fprintf（1‘[X S Y dist] = OptSpace（A）\n‘）;
	return;
end	

rescal_param = sqrt（ nnz（E） * r / norm（M_E‘fro‘）^2 ） ;
M_E = M_E * rescal_param ;

fprintf（1‘Trimming ...\n‘）;
% Trimming

M_Et = M_E ;
d = sum（E）;
d_=mean（full（d））;
for col=1:m
    if （ sum（E（:col））>2*d_ ）
        list = find（ E（:col） > 0 ）;
        p = randperm（length（list））;
        M_Et（ list（ p（ceil（2*d_）:end） ）  col ） = 0;
    end
end

d = sum（E‘）;
d_= mean（full（d））;
for row=1:n
    if （ sum（E（row:））>2*d_ ）
        list = find（ E（row:） > 0 ）;
        p = randperm（length（list））;
        M_Et（rowlist（ p（ceil（2*d_）:end） ） ） = 0;
    end
end

fprintf（1‘Sparse SVD ...\n‘）;
% Sparse SVD
[X0 S0 Y0] = svds（M_Etr） ;

clear M_Et;

% Initial Guess
X0 = X0*sqrt（n） ; Y0 = Y0*sqrt（m） ;
S0 = S0 / eps ;


fprintf（1‘Iteration\tFit Error\n‘）;

% Gradient Descent
X = X0;Y=Y0;
S = getoptS（XYM_EE）;


dist（1） = norm（ （M_E - X*S*Y‘）.*E ‘fro‘）/sqrt（nnz（E） ）  ;
fprintf（1‘0\t\t%e\n‘dist（1） ） ;

for i = 1:niter

% Compute the Gradient 
	[W Z] = gradF_t（XYSM_EEm0rho）;

% Line search for the optimum jump 

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件       35147  2010-12-21 01:47  OptSpace_matlab\COPYING
     文件         983  2010-12-21 01:47  OptSpace_matlab\testing.m~
     文件         982  2010-12-21 01:47  OptSpace_matlab\testing.m
     文件        1159  2010-12-21 01:47  OptSpace_matlab\README
     文件        5696  2010-12-21 01:47  OptSpace_matlab\OptSpace.m
     目录           0  2010-12-21 01:47  OptSpace_matlab\