K-SVD经典字典学习算法

function [Dictionary,output] = KSVD(... Data,... % an nXN matrix that contins N signals (Y), each of dimension n. param) % ========================================================================= % K-SVD algorithm % ========================================================================= % The K-SVD algorithm finds a dictionary for linear representation of % signals. Given a set of signals, it searches for the best dictionary that % can sparsely represent each signal. Detailed discussion on the algorithm % and possible applications can be found in "The K-SVD: An Algorithm for % Designing of Overcomplete Dictionaries for Sparse Representation", written % by M. Aharon, M. Elad, and A.M. Bruckstein and appeared in the IEEE Trans. % On Signal Processing, Vol. 54, no. 11, pp. 4311-4322, November 2006. % ========================================================================= % INPUT ARGUMENTS: % Data an nXN matrix that contins N signals (Y), each of dimension n. % param structure that includes all required % parameters for the K-SVD execution. % Required fields are: % K, ... the number of dictionary elements to train % numIteration,... number of iterations to perform. % errorFlag... if =0, a fix number of coefficients is % used for representation of each signal. If so, param.L must be % specified as the number of representing atom. if =1, arbitrary number % of atoms represent each signal, until a specific representation error % is reached. If so, param.errorGoal must be specified as the allowed % error. % preserveDCAtom... if =1 then the first atom in the dictionary % is set to be constant, and does not ever change. This % might be useful for working with natural % images (in this case, only param.K-1 % atoms are trained). % (optional, see errorFlag) L,... % maximum coefficients to use in OMP coefficient calculations. % (optional, see errorFlag) errorGoal, ... % allowed representation error in representing each signal. % InitializationMethod,... mehtod to initialize the dictionary, can % be one of the following arguments: % * 'DataElements' (initialization by the signals themselves), or: % * 'GivenMatrix' (initialization by a given matrix param.initialDictionary). % (optional, see InitializationMethod) initialDictionary,... % if the initialization method % is 'GivenMatrix', this is the matrix that will be used. % (optional) TrueDictionary, ... % if specified, in each % iteration the difference between this dictionary and the trained one % is measured and displayed. % displayProgress, ... if =1 progress information is displyed. If param.errorFlag==0, % the average repersentation error (RMSE) is displayed, while if % param.errorFlag==1, the average number of required coefficients for % representation of each signal is displayed. % ========================================================================= % OUTPUT ARGUMENTS: % Dictionary The extracted dictionary of size nX(param.K). % output Struct that contains information about the current run. It may include the following fields: % CoefMatrix The final coefficients matrix (it should hold that Data equals approximately Dictionary*output.CoefMatrix. % ratio If the true dictionary was defined (in % synthetic experiments), this parameter holds a vector of length % param.numIteration that includes the detection ratios in each % iteration). % totalerr The total representation error after each % iteration (defined only if % param.displayProgress=1 and % param.errorFlag = 0) % numCoef A vector of length param.numIteration that % include the average number of coefficients required for representation % of each signal (in each iteration) (defined only if % param.displayProgress=1 and % param.errorFlag = 1) % ========================================================================= if (~isfield(param,'displayProgress')) param.displayProgress = 0; end totalerr(1) = 99999; if (isfield(param,'errorFlag')==0) param.errorFlag = 0; end if (isfield(param,'TrueDictionary')) displayErrorWithTrueDictionary = 1; ErrorBetweenDictionaries = zeros(param.numIteration+1,1); ratio = zeros(param.numIteration+1,1); else displayErrorWithTrueDictionary = 0; ratio = 0; end if (param.preserveDCAtom>0) FixedDictionaryElement(1:size(Data,1),1) = 1/sqrt(size(Data,1)); else FixedDictionaryElement = []; end % coefficient calculation method is OMP with fixed number of coefficients if (size(Data,2) < param.K) disp('Size of data is smaller than the dictionary size. Trivial solution...'); Dictionary = Data(:,1:size(Data,2)); return; elseif (strcmp(param.InitializationMethod,'DataElements')) Dictionary(:,1:param.K-param.preserveDCAtom) = Data(:,1:param.K-param.preserveDCAtom); elseif (strcmp(param.InitializationMethod,'GivenMatrix')) Dictionary(:,1:param.K-param.preserveDCAtom) = param.initialDictionary(:,1:param.K-param.preserveDCAtom); end % reduce the components in Dictionary that are spanned by the fixed % elements if (param.preserveDCAtom) tmpMat = FixedDictionaryElement \ Dictionary; Dictionary = Dictionary - FixedDictionaryElement*tmpMat; end %normalize the dictionary. Dictionary = Dictionary*diag(1./sqrt(sum(Dictionary.*Dictionary))); Dictionary = Dictionary.*repmat(sign(Dictionary(1,:)),size(Dictionary,1),1); % multiply in the sign of the first element. totalErr = zeros(1,param.numIteration); % the K-SVD algorithm starts here. for iterNum = 1:param.numIteration % find the coefficients if (param.errorFlag==0) %CoefMatrix = mexOMPIterative2(Data, [FixedDictionaryElement,Dictionary],param.L); CoefMatrix = OMP([FixedDictionaryElement,Dictionary],Data, param.L); else %CoefMatrix = mexOMPerrIterative(Data, [FixedDictionaryElement,Dictionary],param.errorGoal); CoefMatrix = OMPerr([FixedDictionaryElement,Dictionary],Data, param.errorGoal); param.L = 1; end replacedVectorCounter = 0; rPerm = randperm(size(Dictionary,2)); for j = rPerm [betterDictionaryElement,CoefMatrix,addedNewVector] = I_findBetterDictionaryElement(Data,... [FixedDictionaryElement,Dictionary],j+size(FixedDictionaryElement,2),... CoefMatrix ,param.L); Dictionary(:,j) = betterDictionaryElement; if (param.preserveDCAtom) tmpCoef = FixedDictionaryElement\betterDictionaryElement; Dictionary(:,j) = betterDictionaryElement - FixedDictionaryElement*tmpCoef; Dictionary(:,j) = Dictionary(:,j)./sqrt(Dictionary(:,j)'*Dictionary(:,j)); end replacedVectorCounter