Matrix Completion.m - Revision history

Ranjelin: Reverted edits by Yjoqakyky (Talk); changed back to last version by Dattorro

2010-11-24T04:28:17Z

Reverted edits by Yjoqakyky (Talk); changed back to last version by Dattorro

(Difference between revisions)

Anonymous at 03:55, 24 November 2010

2010-11-24T03:55:48Z

(Difference between revisions)

Dattorro: Protected "Matrix Completion.m" [edit=autoconfirmed:move=autoconfirmed]

2009-11-15T20:20:46Z

Protected "Matrix Completion.m" [edit=autoconfirmed:move=autoconfirmed]

←Older revision

Revision as of 20:20, 15 November 2009

Dattorro: Undo revision 1755 by 61.145.121.124 (Talk)

2009-11-15T20:19:26Z

Undo revision 1755 by 61.145.121.124 (Talk)

←Older revision		Revision as of 20:19, 15 November 2009
Line 1:		Line 1:
-	~~ljSUCg <a href~~="http://~~rublcsxccwog~~.~~com~~/~~">rublcsxccwog<~~/a>, [~~url=~~http://~~hxhjkyoczrvm~~.~~com~~/]~~hxhjkyoczrvm~~[/~~url~~], [~~link=~~http://~~dylpgublymxu~~.~~com/~~]~~dylpgublymxu~~[/~~link~~], ~~http~~://~~enlwofelvhif~~.~~com~~/	+	== Matlab demonstration of [http://www.temasek-lab.nus.edu.sg/~tslcaij Cai], [http://www.acm.caltech.edu/~emmanuel Candès], & [http://www.math.nus.edu.sg/~matzuows Shen] ==
		+	[http://arxiv.org/abs/0810.3286 A Singular Value Thresholding Algorithm for Matrix Completion, 2008]
		+
		+	This Matlab code below is working, complete, debugged, and corresponds to the paper cited above.
		+	It is capable of solving smaller matrix completion problems quite well, as the demonstration program shows.
		+
		+	[http://svt.caltech.edu Singular Value Thresholding (SVT) code] for solving larger completion problems is presently under development.
		+	It is written in C and Fortran and can be compiled in Matlab. [[Talk:Matrix_Completion.m\|Read more...]]
		+
		+	<pre>
		+	% Written by: Emmanuel Candes
		+	% Email: emmanuel@acm.caltech.edu
		+	% Created: October 2008
		+
		+	%% Setup a matrix
		+	randn('state',2008);
		+	rand('state',2008);
		+
		+	n = 1000; r = 10;
		+	M = randn(n,r)*randn(r,n);
		+
		+	df = r(2n-r);
		+	oversampling = 5; m = 5*df;
		+
		+	Omega = randsample(n^2,m);
		+	data = M(Omega);
		+
		+	%% Set parameters and solve
		+
		+	p = m/n^2; delta = 1.2/p;
		+	maxiter = 500;
		+	tol = 1e-4;
		+
		+	%% Approximate minimum nuclear norm solution by SVT algorithm
		+
		+	tic
		+	[U,S,V,numiter] = SVT(n,Omega,data,delta,maxiter,tol);
		+	toc
		+
		+	%% Show results
		+
		+	X = USV';
		+
		+	disp(sprintf('The relative error on Omega is: %d ', norm(data-X(Omega))/norm(data)))
		+	disp(sprintf('The relative recovery error is: %d ', norm(M-X,'fro')/norm(M,'fro')))
		+	disp(sprintf('The relative recovery in the spectral norm is: %d ', norm(M-X)/norm(M)))
		+	</pre>
		+
		+	=== SVT() ===
		+	<pre>
		+	function [U,Sigma,V,numiter] = SVT(n,Omega,b,delta,maxiter,tol)
		+	%
		+	% Finds the minimum of tau \|\|X\|\|_* + .5 \|\| X \|\|_F^2
		+	% subject to P_Omega(X) == P_Omega(M)
		+	% using linear Bregman iterations
		+	%
		+	% Usage: [U,S,V,numiter] = SVT(n,Omega,b,delta,maxiter,opts)
		+	%
		+	% Inputs:
		+	% n - size of the matrix X assumed n by n
		+	% Omega - set of observed entries
		+	% b - data vector of the form M(Omega)
		+	% delta - step size
		+	% maxiter - maximum number of iterations
		+	%
		+	% Outputs: matrix X stored in SVD format X = Udiag(S)V'
		+	% U - nxr left singular vectors
		+	% S - rx1 singular values
		+	% V - nxr right singular vectors
		+	% numiter - number of iterations to achieve convergence
		+
		+	% Description:
		+	% Reference:
		+	%
		+	% Cai, Candes and Shen
		+	% A singular value thresholding algorithm for matrix completion
		+	% Submitted for publication, October 2008.
		+	%
		+	% Written by: Emmanuel Candes
		+	% Email: emmanuel@acm.caltech.edu
		+	% Created: October 2008
		+
		+	m = length(Omega); [temp,indx] = sort(Omega);
		+	tau = 5*n; incre = 5;
		+
		+	[i, j] = ind2sub([n,n], Omega);
		+	ProjM = sparse(i,j,b,n,n,m);
		+
		+	normProjM = normest(ProjM);
		+	k0 = ceil(tau/(delta*normProjM));
		+
		+	normb = norm(b);
		+
		+	y = k0deltab;
		+	Y = sparse(i,j,y,n,n,m);
		+	r = 0;
		+
		+	fprintf('\nIteration: ');
		+	for k = 1:maxiter
		+	fprintf('\b\b\b%3d',k);
		+	s = r + 1;
		+
		+	OK = 0;
		+	while ~OK
		+	[U,Sigma,V] = lansvd(Y,s,'L');
		+	OK = Sigma(s,s) <= tau;
		+	s = s + incre;
		+	end
		+
		+	sigma = diag(Sigma); r = sum(sigma > tau);
		+	U = U(:,1:r); V = V(:,1:r); sigma = sigma(1:r) - tau; Sigma = diag(sigma);
		+
		+	A = Udiag(sigma)V';
		+	x = A(Omega);
		+
		+	if norm(x-b)/normb < tol
		+	break
		+	end
		+
		+	y = y + delta*(b-x);
		+	updateSparse(Y,y,indx);
		+	end
		+
		+	fprintf('\n');
		+	numiter = k;
		+	</pre>

	== subroutines ==		== subroutines ==

61.145.121.124: /* Matlab demonstration of [http://www.temasek-lab.nus.edu.sg/~tslcaij Cai], [http://www.acm.caltech.edu/~emmanuel Candès], & [http://www.math.nus.edu.sg/~matzuows Shen] */

2009-11-15T10:53:42Z