1function [s, err_mse, iter_time]=greed_omp_chol(x,A,m,varargin) 2%-*- texinfo -*- 3%@deftypefn {Function} greed_omp_chol 4%@verbatim 5% greed_omp_chol: Orthogonal Matching Pursuit algorithm based on Cholesky 6% factorisation 7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 8% Usage 9% [s, err_mse, iter_time]=greed_omp_chol(x,P,m,'option_name','option_value') 10%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 11%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 12% Input 13% Mandatory: 14% x Observation vector to be decomposed 15% P Either: 16% 1) An nxm matrix (n must be dimension of x) 17% 2) A function handle (type "help function_format" 18% for more information) 19% Also requires specification of P_trans option. 20% 3) An object handle (type "help object_format" for 21% more information) 22% m length of s 23% 24% Possible additional options: 25% (specify as many as you want using 'option_name','option_value' pairs) 26% See below for explanation of options: 27%__________________________________________________________________________ 28% option_name AVAILABLE OPTION_VALUES default 29%-------------------------------------------------------------------------- 30% stopCrit M, CORR, MSE, MSE_CHANGE M 31% stopTol NUMBER (SEE BELOW) n/4 32% P_trans FUNCTION_HANDLE (SEE BELOW) 33% maxIter POSITIVE INTEGER (SEE BELOW) n 34% verbose TRUE, FALSE false 35% start_val VECTOR OF LENGTH M zeros 36% 37% Available stopping criteria : 38% M - Extracts exactly M = stopTol elements. 39% corr - Stops when maximum correlation between 40% residual and atoms is below stopTol value. 41% mse - Stops when mean squared error of residual 42% is below stopTol value. 43% mse_change - Stops when the change in the mean squared 44% error falls below stopTol value. 45% 46% stopTol: Value for stopping criterion. 47% 48% P_trans: If P is a function handle, then P_trans has to be specified and 49% must be a function handle. 50% 51% maxIter: Maximum number of allowed iterations. 52% 53% verbose: Logical value to allow algorithm progress to be displayed. 54% 55% start_val: Allows algorithms to start from partial solution. 56% 57%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 58% Outputs 59% s Solution vector 60% err_mse Vector containing mse of approximation error for each 61% iteration 62% iter_time Vector containing computation times for each iteration 63% 64%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 65% Description 66% greed_omp_chol performs a greedy signal decomposition. 67% In each iteration a new element is selected depending on the inner 68% product between the current residual and columns in P. 69% The non-zero elements of s are approximated by orthogonally projecting 70% x onto the selected elements in each iteration. 71% The algorithm uses Cholesky factorisation to calculate the required 72% matrix inverses. 73% 74% See Also 75% greed_qr, greed_omp_cg, greed_omp_cgp, greed_omp_pinv, 76% greed_omp_linsolve, greed_gp, greed_nomp 77% 78% Copyright (c) 2007 Thomas Blumensath 79% 80% The University of Edinburgh 81% Email: thomas.blumensath@ed.ac.uk 82% Comments and bug reports welcome 83% 84% This file is part of sparsity Version 0.1 85% Created: April 2007 86% 87% Part of this toolbox was developed with the support of EPSRC Grant 88% D000246/1 89% 90% Please read COPYRIGHT.m for terms and conditions. 91%@end verbatim 92%@strong{Url}: @url{http://ltfat.github.io/doc/thirdparty/sparsify/private/greed_omp_chol.html} 93%@end deftypefn 94 95% Copyright (C) 2005-2016 Peter L. Soendergaard <peter@sonderport.dk>. 96% This file is part of LTFAT version 2.3.1 97% 98% This program is free software: you can redistribute it and/or modify 99% it under the terms of the GNU General Public License as published by 100% the Free Software Foundation, either version 3 of the License, or 101% (at your option) any later version. 102% 103% This program is distributed in the hope that it will be useful, 104% but WITHOUT ANY WARRANTY; without even the implied warranty of 105% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 106% GNU General Public License for more details. 107% 108% You should have received a copy of the GNU General Public License 109% along with this program. If not, see <http://www.gnu.org/licenses/>. 110 111%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 112% Default values and initialisation 113%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 114 115 116[n1 n2]=size(x); 117if n2 == 1 118 n=n1; 119elseif n1 == 1 120 x=x'; 121 n=n2; 122else 123 display('x must be a vector.'); 124 return 125end 126 127sigsize = x'*x/n; 128initial_given=0; 129err_mse = []; 130iter_time = []; 131STOPCRIT = 'M'; 132STOPTOL = ceil(n/4); 133MAXITER = n; 134verbose = false; 135s_initial = zeros(m,1); 136vectnfact = ones(m,1); 137linsolve_options_transpose.UT = true; 138linsolve_options_transpose.TRANSA = true; 139linsolve_options.UT = true; 140r_count=0; 141 142 143if verbose 144 display('Initialising...') 145end 146 147%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 148% Output variables 149%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 150 151switch nargout 152 case 3 153 comp_err=true; 154 comp_time=true; 155 case 2 156 comp_err=true; 157 comp_time=false; 158 case 1 159 comp_err=false; 160 comp_time=false; 161 case 0 162 error('Please assign output variable.') 163 otherwise 164 error('Too many output arguments specified') 165end 166 167%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 168% Look through options 169%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 170 171% Put option into nice format 172Options={}; 173OS=nargin-3; 174c=1; 175for i=1:OS 176 if isa(varargin{i},'cell') 177 CellSize=length(varargin{i}); 178 ThisCell=varargin{i}; 179 for j=1:CellSize 180 Options{c}=ThisCell{j}; 181 c=c+1; 182 end 183 else 184 Options{c}=varargin{i}; 185 c=c+1; 186 end 187end 188OS=length(Options); 189if rem(OS,2) 190 error('Something is wrong with argument name and argument value pairs.') 191end 192 193for i=1:2:OS 194 switch Options{i} 195 case {'stopCrit'} 196 if (strmatch(Options{i+1},{'M'; 'corr'; 'mse'; 'mse_change'},'exact')); 197 STOPCRIT = Options{i+1}; 198 else error('stopCrit must be char string [M, corr, mse, mse_change]. Exiting.'); end 199 case {'stopTol'} 200 if isa(Options{i+1},'numeric') ; STOPTOL = Options{i+1}; 201 else error('stopTol must be number. Exiting.'); end 202 case {'P_trans'} 203 if isa(Options{i+1},'function_handle'); Pt = Options{i+1}; 204 else error('P_trans must be function _handle. Exiting.'); end 205 case {'maxIter'} 206 if isa(Options{i+1},'numeric'); MAXITER = Options{i+1}; 207 else error('maxIter must be a number. Exiting.'); end 208 case {'verbose'} 209 if isa(Options{i+1},'logical'); verbose = Options{i+1}; 210 else error('verbose must be a logical. Exiting.'); end 211 case {'vecNormFac'} 212 if isa(Options{i+1},'numeric')& length(Options{i+1}) == m , vectnfact = Options{i+1}; 213 else error('verbose must be a logical. Exiting.'); end 214 case {'start_val'} 215 if isa(Options{i+1},'numeric') & length(Options{i+1}) == m ; 216 s_initial = Options{i+1}; 217 initial_given=1; 218 else error('start_val must be a vector of length m. Exiting.'); end 219 otherwise 220 error('Unrecognised option. Exiting.') 221 end 222end 223 224 225 226if strcmp(STOPCRIT,'M') 227 maxM=STOPTOL; 228else 229 maxM=MAXITER; 230end 231 232if nargout >=2 233 err_mse = zeros(maxM,1); 234end 235if nargout ==3 236 iter_time = zeros(maxM,1); 237end 238 239 240 241%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 242% Make P and Pt functions 243%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 244 245if isa(A,'float') P =@(z) A*z; Pt =@(z) A'*z; 246elseif isobject(A) P =@(z) A*z; Pt =@(z) A'*z; 247elseif isa(A,'function_handle') 248 try 249 if isa(Pt,'function_handle'); P=A; 250 else error('If P is a function handle, Pt also needs to be a function handle. Exiting.'); end 251 catch error('If P is a function handle, Pt needs to be specified. Exiting.'); end 252else error('P is of unsupported type. Use matrix, function_handle or object. Exiting.'); end 253 254 255% This vector is used repeatedly, so pre-calculate; 256Ptx=Pt(x); 257 258 259 260%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 261% Random Check to see if dictionary is normalised 262%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 263 264% mask=zeros(m,1); 265% mask(ceil(rand*m))=1; 266% nP=norm(P(mask)); 267% if abs(1-nP)>1e-3; 268% display('Dictionary appears not to have unit norm columns.') 269% end 270 271%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 272% Check if we have enough memory and initialise 273%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 274 275 276try R=zeros(maxM); 277catch error('Variable size is too large. Please try greed_omp_cg algorithm or reduce MAXITER.') 278end 279 280%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 281% Do we start from zero or not? 282%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 283 284if initial_given ==1; 285 IN=find(s_initial); 286else 287 IN=[]; 288end 289if numel(IN) == 0 290 s_initial = zeros(m,1); 291 Residual=x; 292 s=s_initial; 293 R=[]; 294 oldERR = sigsize; 295else 296 R(1,1)=UpdateCholesky([],P,Pt,IN(1),m); 297 r_count = r_count + 1; 298 for i=2:length(IN) 299 R(1:r_count+1,1:r_count+1)=UpdateCholesky(R(1:r_count,1:r_count),P,Pt,IN(1:i),m); 300 r_count = r_count + 1; 301 end 302 s = zeros(m,1); 303 Rs = linsolve(R(1:r_count,1:r_count),Ptx(IN),linsolve_options_transpose); 304 s(IN) = linsolve(R(1:r_count,1:r_count),Rs,linsolve_options); 305 Residual=x-P(s); 306 oldERR = Residual'*Residual/n; 307end 308 309 310 311%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 312% Main algorithm 313%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 314if verbose 315 display('Main iterations...') 316end 317 318 319 320tic 321t=0; 322DR=Pt(Residual).*vectnfact; 323done = 0; 324iter=1; 325while ~done 326 327 % Select new element 328 DR(IN)=0; 329 [~, I]=max(abs(DR)); 330 IN=[IN I]; 331 332 % Update R 333 R(1:r_count+1,1:r_count+1)=UpdateCholesky(R(1:r_count,1:r_count),P,Pt,IN,m); 334 r_count = r_count + 1; 335 336 337% Pmat=zeros(n,length(IN)); 338% for i=1:length(IN) 339% mask=zeros(m,1); 340% mask(IN(i))=1; 341% Pmat(:,i)=P(mask); 342% end 343% R_real=chol(Pmat'*Pmat) 344% R 345% pause 346% 347 % Solve for s 348 Rs = linsolve(R(1:r_count,1:r_count),Ptx(IN),linsolve_options_transpose); 349 s(IN) = linsolve(R(1:r_count,1:r_count),Rs,linsolve_options); 350 351 % New Residual and inner products 352 353 Residual=x-P(s); 354 DR=Pt(Residual).*vectnfact; 355 356 ERR=Residual'*Residual/n; 357 if comp_err 358 err_mse(iter)=ERR; 359 end 360 361 if comp_time 362 iter_time(iter)=toc; 363 end 364 365%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 366% Are we done yet? 367%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 368 369 if strcmp(STOPCRIT,'M') 370 if iter >= STOPTOL 371 done =1; 372 elseif verbose && toc-t>10 373 display(sprintf('Iteration %i. --- %i iterations to go',iter ,STOPTOL-iter)) 374 t=toc; 375 end 376 elseif strcmp(STOPCRIT,'mse') 377 if comp_err 378 if err_mse(iter)<STOPTOL; 379 done = 1; 380 elseif verbose && toc-t>10 381 display(sprintf('Iteration %i. --- %i mse',iter ,err_mse(iter))) 382 t=toc; 383 end 384 else 385 if ERR<STOPTOL; 386 done = 1; 387 elseif verbose && toc-t>10 388 display(sprintf('Iteration %i. --- %i mse',iter ,ERR)) 389 t=toc; 390 end 391 end 392 elseif strcmp(STOPCRIT,'mse_change') && iter >=2 393 if comp_err && iter >=2 394 if ((err_mse(iter-1)-err_mse(iter))/sigsize <STOPTOL); 395 done = 1; 396 elseif verbose && toc-t>10 397 display(sprintf('Iteration %i. --- %i mse change',iter ,(err_mse(iter-1)-err_mse(iter))/sigsize )) 398 t=toc; 399 end 400 else 401 if ((oldERR - ERR)/sigsize < STOPTOL); 402 done = 1; 403 elseif verbose && toc-t>10 404 display(sprintf('Iteration %i. --- %i mse change',iter ,(oldERR - ERR)/sigsize)) 405 t=toc; 406 end 407 end 408 elseif strcmp(STOPCRIT,'corr') 409 if max(abs(DR)) < STOPTOL; 410 done = 1; 411 elseif verbose && toc-t>10 412 display(sprintf('Iteration %i. --- %i corr',iter ,max(abs(DR)))) 413 t=toc; 414 end 415 end 416 417 % Also stop if residual gets too small or maxIter reached 418 if comp_err 419 if err_mse(iter)<1e-16 420 display('Stopping. Exact signal representation found!') 421 done=1; 422 end 423 else 424 425 426 if iter>1 427 if ERR<1e-16 428 display('Stopping. Exact signal representation found!') 429 done=1; 430 end 431 end 432 end 433 434 if iter >= MAXITER 435 display('Stopping. Maximum number of iterations reached!') 436 done = 1; 437 end 438 439%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 440% If not done, take another round 441%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 442 443 if ~done 444 iter=iter+1; 445 oldERR=ERR; 446 end 447end 448 449%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 450% Only return as many elements as iterations 451%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 452 453if nargout >=2 454 err_mse = err_mse(1:iter); 455end 456if nargout ==3 457 iter_time = iter_time(1:iter); 458end 459if verbose 460 display('Done') 461end 462 463% Change history 464% 465% 8 of Februray: Algo does no longer stop if dictionary is not normaliesd. 466