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|）?%????????-?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\