MatrixCompletion

用svt 和 fpc进行的矩阵恢复算法，matlab版。

function [USVnumiter]  = FPC（nOmegabmu_finalmaxitertol）
% [USigmaVnumiter]  = FPC（nOmegabmu_finalmaxitergtol）
%
% Finds mininum  mu ||X||_* + 1/2 || A（X） - b ||_2^2
%
%   where A（X） is the projection of X onto the set of indices
%   in Omega.
%
% For efficiency the algorithm uses continuation （i.e. a series of
%   mu aka the “outer loop“） until mu = mu_final.
%
% maxiter controls maximum number of iterations per inner loop
%
% Outputs:
%   UV and Sigma are singular vectors and singular values where
%       X = U*Sigma*V‘
%   numiter is the number of iterations over all inner and outer loops

% Reference:
%
%   “Fixed point and Bregman iterative methods for matrix
%       rank minimization.“
%   Shiquian Ma Donald Goldfarb Lifeng Chen October 2008
%   ftp://ftp.math.ucla.edu/pub/camreport/cam08-78.pdf

% code by Stephen Becker srbecker@caltech.edu March 2009

% May 2009: adding support for complex matrices


% -- some parameters:
tau = 1.99;  % recommended that tau is between 1 and 2
eta_mu = 1/4;   % how much to decrease mu at every step

%VERBOSE = false;  % no output
VERBOSE = 1;    % a little bit of output
VERBOSE = 2;    % even more output



if nargin < 6 || isempty（tol）
    tol = 1e-4;
end
if nargin < 5 || isempty（maxiter）
    maxiter = 500;
end
    
if length（n） == 1
    n1 = n（1）; n2 = n1;
elseif length（n） == 2
    n1 = n（1）; n2 = n（2）;
end
if n1*n2 < 100*100
    SMALLSCALE = true; 
    X = zeros（n1n2）;
else
    SMALLSCALE = false;
end


m = length（Omega）; [tempindx] = sort（Omega）; 
incre = 5;
r = 1; s = r + 1;  % estimate new rank
normb = norm（b）;

[i j] = ind2sub（[n1n2] Omega）;
G = sparse（ijbn1n2m）;  % i.e. starting with X = 0;
mu = normest（ G  1e-2 ）;

% What the best way to multiply a sparse matrix?
[forwardType transposeType] = findBestMultiply（G.2）;

U = zeros（n11）;
V = zeros（n21）;
S = 0;
relResid = 2;

if VERBOSE fprintf（‘**************************************\n‘）; end
numiter = 0;
while mu > mu_final
    mu = max（mu * eta_mumu_final）;
    if VERBOSE fprintf（‘FPC mu = %f\n‘mu）; end
    if VERBOSE == 1 fprintf（‘\tIteration:      ‘）; end
    s = 2*r + 1;  % estimate new rank for next iteration
for k = 1:maxiter
    numiter = numiter + 1;
    if VERBOSE==1 fprintf（‘\b\b\b\b%4d‘k）;  end

    % Make routines for multiplying by a sparse matrix
    Gt = G‘;
    switch forwardType
        case 1 Gforward = @（x） G*x;
        case 2 Gforward = @（x） Gt‘*x;
        case 3 Gforward = @（x） smvp（Gx）;
    end
    switch transposeType 
        case 1 Gtranspose = @（x） Gt*x;
        case 2 Gtranspose = @（x） G‘*x;
        case 3 Gtranspose = @（x） smvp（Gtx）;
    end
    
    % Y = X - tau*G
    Y = @（x） U*（S*（V‘*x）） - tau*Gforward（x）;
    Yt= @（x） V*（S*（U‘*x）） - tau*Gtranspose（x）;
    
    % Perform a SVD
    if SMALLSCALE
        [USigmaV] = svd（full（X - tau*G）‘econ‘）;
    else
        OK = 0;
        while ~OK
            opts = []; 
            if ~isreal（G） opts.eta = 1e-16; end
%     

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        7036  2009-05-27 22:59  SVT.m
     文件        5167  2009-05-27 23:03  FPC.m
     文件        3904  2009-05-27 23:00  Test_SVT.m
     文件         985  2009-02-22 02:15  private\bdsqr.m
     文件       11748  2009-05-20 17:17  private\bdsqr.mexa64
     文件        3016  2009-03-24 16:20  private\bdsqr_mex.c
     文件        8049  2009-05-28 01:12  private\bdsqr.mexglx
     文件       14072  2009-03-04 20:44  private\bdsqr.mexmaci
     文件       25208  2009-02-22 02:15  private\bdsqr.mexsg
     文件       26109  2009-02-22 02:15  private\bdsqr.mexsg64
     文件       95852  2009-02-22 02:15  private\bdsqr.mexsol
     文件       55808  2009-03-14 23:23  private\bdsqr.mexw32
     文件        1504  2009-03-14 23:23  private\compute_int.m
     文件        1346  2009-02-22 02:15  private\dbdqr.c
     文件         445  2009-02-22 02:15  private\dbdqr.f
     文件        2056  2009-05-13 23:31  private\findBestMultiply.m
     文件       14907  2009-05-28 01:12  private\install_mex.m
     文件       23704  2009-05-14 00:02  private\lanbpro.m
     文件       11964  2009-05-13 23:32  private\lansvd.m
     文件         939  2009-03-04 22:44  private\refinebounds.m
     文件        3488  2009-03-08 01:58  private\reorth.c
     文件        2906  2009-05-13 23:33  private\reorth_complex.m
     文件        3580  2009-03-04 22:44  private\reorth.f
     文件        2661  2009-03-04 22:44  private\reorth.m
     文件       12000  2009-05-20 17:17  private\reorth.mexa64
     文件        3573  2009-03-24 16:15  private\reorth_mex.c
     文件        8069  2009-05-28 01:12  private\reorth.mexglx
     文件       21268  2009-03-04 22:44  private\reorth.mexmaci
     文件       25428  2009-03-04 22:44  private\reorth.mexsg
     文件       26694  2009-03-04 22:44  private\reorth.mexsg64
     文件       86872  2009-03-04 22:44  private\reorth.mexsol
............此处省略22个文件信息