SVT原始代码

基于奇异值阈值的矩阵填充算法原始代码。附带了一个FPC算法进行比较。

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
%     

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-01-26 21:32  SVT_MostRecent\
     文件        5167  2009-05-28 07:03  SVT_MostRecent\FPC.m
     目录           0  2015-12-16 10:01  SVT_MostRecent\private\
     文件         986  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.m
     文件        9263  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexa64
     文件       14563  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexglx
     文件       13200  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexmac
     文件        9261  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexmaci
     文件        9152  2011-04-26 00:39  SVT_MostRecent\private\bdsqr.mexmaci64
     文件       25208  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexsg
     文件       26109  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexsg64
     文件       95852  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexsol
     文件       56832  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexw32
     文件       57344  2010-01-25 13:26  SVT_MostRecent\private\bdsqr.mexw64
     文件        4686  2010-01-25 13:26  SVT_MostRecent\private\bdsqr_mex.c
     文件        1504  2010-01-25 13:26  SVT_MostRecent\private\compute_int.m
     文件        1346  2010-01-25 13:26  SVT_MostRecent\private\dbdqr.c
     文件         445  2009-02-22 10:15  SVT_MostRecent\private\dbdqr.f
     文件        2160  2010-01-25 13:26  SVT_MostRecent\private\findBestMultiply.m
     文件        4124  2011-04-26 00:48  SVT_MostRecent\private\install_mex.m
     文件       23704  2010-01-25 13:26  SVT_MostRecent\private\lanbpro.m
     文件       12309  2010-01-25 13:26  SVT_MostRecent\private\lansvd.m
     文件         173  2010-01-25 13:26  SVT_MostRecent\private\mexHelper.m
     文件         939  2010-01-25 13:26  SVT_MostRecent\private\refinebounds.m
     文件        4433  2010-01-25 13:26  SVT_MostRecent\private\reorth.c
     文件        3580  2009-03-05 06:44  SVT_MostRecent\private\reorth.f
     文件        2714  2010-01-25 13:26  SVT_MostRecent\private\reorth.m
     文件        9332  2010-01-25 13:26  SVT_MostRecent\private\reorth.mexa64
     文件       16160  2010-01-25 13:26  SVT_MostRecent\private\reorth.mexglx
     文件       13276  2010-01-25 13:26  SVT_MostRecent\private\reorth.mexmac
     文件       21268  2010-01-25 13:26  SVT_MostRecent\private\reorth.mexmaci
............此处省略51个文件信息