K-SVD 也是利用 Block Coordinate Descent。在字典更新阶段,也同时更新系数矩阵中的非零系数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
%KSVD K-SVD dictionary training. % [D,GAMMA] = KSVD(PARAMS) runs the K-SVD dictionary training algorithm on % the specified set of signals, returning the trained dictionary D and the % signal representation matrix GAMMA. % % KSVD has two modes of operation: sparsity-based and error-based. For % sparsity-based minimization, the optimization problem is given by % % min |X-D*GAMMA|_F^2 s.t. |Gamma_i|_0 <= T % D,Gamma % % where X is the set of training signals, Gamma_i is the i-th column of % Gamma, and T is the target sparsity. For error-based minimization, the % optimization problem is given by % % min |Gamma|_0 s.t. |X_i - D*Gamma_i|_2 <= EPSILON % D,Gamma % % where X_i is the i-th training signal, and EPSILON is the target error. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
% 'memusage' - Memory usage. % This parameter controls memory usage of the function. 'memusage' % should be one of the strings 'high', 'normal' (default) or 'low'. % When set to 'high', the fastest implementation of OMP is used, which % involves precomputing both G=D'*D and DtX=D'*X. This increasese % speed but also requires a significant amount of memory. When set to % 'normal', only the matrix G is precomputed, which requires much less % memory but slightly decreases performance. Finally, when set to % 'low', neither matrix is precomputed. This should only be used when % the trained dictionary is highly redundant and memory resources are % very low, as this will dramatically increase runtime. See function % OMP for more details. % % 'codemode' - Sparse-coding target mode. % Specifies whether the 'Tdata' or 'Edata' fields should be used for % the sparse-coding stopping criterion. This is useful when both % fields are present in PARAMS. 'codemode' should be one of the % strings 'sparsity' or 'error'. If it is not present, and both fields % are specified, sparsity-based coding takes place. % % 'exact' - Exact K-SVD update. % Specifies whether the exact or approximate dictionary update % should be used. By default, the approximate computation is used, % which is significantly faster and requires less memory. Specifying a % nonzero value for 'exact' causes the exact computation to be used % instead, which slows down the method but provides slightly improved % results. The exact update uses SVD to solve the rank-1 minimization % problem, while the approximate upate performs alternate-optimization % to solve this problem. |
参数设置
1 2 3 4 |
ksvd_conf.iternum = 40; % TBD ksvd_conf.memusage = 'normal'; % higher usage doesn't fit... ksvd_conf.dictsize = 1000; % TBD ksvd_conf.Tdata = 3; % maximal sparsity: TBD |
matlab全局变量设置
1 2 3 4 5 6 7 8 9 10 |
global CODE_SPARSITY CODE_ERROR codemode global MEM_LOW MEM_NORMAL MEM_HIGH memusage global ompfunc ompparams exactsvd CODE_SPARSITY = 1; CODE_ERROR = 2; MEM_LOW = 1; MEM_NORMAL = 2; MEM_HIGH = 3; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
%%%%% parse input parameters %%%%% data = params.data; ompparams = {}; % coding mode % if (isfield(params,'codemode')) switch lower(params.codemode) case 'sparsity' codemode = CODE_SPARSITY; thresh = params.Tdata; case 'error' codemode = CODE_ERROR; thresh = params.Edata; otherwise error('Invalid coding mode specified'); end elseif (isfield(params,'Tdata')) codemode = CODE_SPARSITY; thresh = params.Tdata; elseif (isfield(params,'Edata')) codemode = CODE_ERROR; thresh = params.Edata; else error('Data sparse-coding target not specified'); end % max number of atoms % if (codemode==CODE_ERROR && isfield(params,'maxatoms')) ompparams{end+1} = 'maxatoms'; ompparams{end+1} = params.maxatoms; end % memory usage % ... % iteration count % .... % omp function % if (codemode == CODE_SPARSITY) ompfunc = @omp; else ompfunc = @omp2; end ....%省略部分代码 % exact svd computation % exactsvd = 0; if (isfield(params,'exact') && params.exact~=0) exactsvd = 1; end |
1 2 3 4 5 6 7 8 9 |
function y = normcols(x) %NORMCOLS Normalize matrix columns. %Y = NORMCOLS(X) normalizes the columns of X to unit length, returning %the result as Y. y = x*spdiag(1./sqrt(sum(x.*x))); |
作rank1-svd
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
function [atom,gamma_j,data_indices,unused_sigs,replaced_atoms] = optimize_atom(X,D,j,Gamma,unused_sigs,replaced_atoms) global exactsvd % data samples which use the atom, and the corresponding nonzero % coefficients in Gamma [gamma_j, data_indices] = sprow(Gamma, j); if (length(data_indices) < 1) maxsignals = 5000; perm = randperm(length(unused_sigs)); perm = perm(1:min(maxsignals,end)); E = sum((X(:,unused_sigs(perm)) - D*Gamma(:,unused_sigs(perm))).^2); [d,i] = max(E); atom = X(:,unused_sigs(perm(i))); atom = atom./norm(atom); gamma_j = zeros(size(gamma_j)); unused_sigs = unused_sigs([1:perm(i)-1,perm(i)+1:end]); replaced_atoms(j) = 1; return; end smallGamma = Gamma(:,data_indices); Dj = D(:,j); if (exactsvd) %计算最大的奇异值,作rank1-svd [atom,s,gamma_j] = svds(X(:,data_indices) - D*smallGamma + Dj*gamma_j, 1); gamma_j = s*gamma_j; else atom = collincomb(X,data_indices,gamma_j') - D*(smallGamma*gamma_j') + Dj*(gamma_j*gamma_j'); atom = atom/norm(atom); gamma_j = rowlincomb(atom,X,1:size(X,1),data_indices) - (atom'*D)*smallGamma + (atom'*Dj)*gamma_j; end end |