annotate solvers/SMALL_ompGabor/ompGabor.m @ 140:31d2864dfdd4 ivand_dev

Audio Impainting additional constraints with cvx added
author Ivan Damnjanovic lnx <ivan.damnjanovic@eecs.qmul.ac.uk>
date Mon, 25 Jul 2011 17:27:05 +0100
parents
children
rev   line source
ivan@140 1 function gamma = omp(varargin)
ivan@140 2 %OMP Sparsity-constrained Orthogonal Matching Pursuit.
ivan@140 3 % GAMMA = OMP(D,X,G,T) solves the optimization problem
ivan@140 4 %
ivan@140 5 % min |X - D*GAMMA|_2 s.t. |GAMMA|_0 <= T
ivan@140 6 % gamma
ivan@140 7 %
ivan@140 8 % for each of the signals in X, using Batch Orthogonal Matching Pursuit.
ivan@140 9 % Here, D is a dictionary with normalized columns, X is a matrix
ivan@140 10 % containing column signals, T is the # of non-zeros in each signal
ivan@140 11 % representation, and G is the Gramm matrix D'*D. The output GAMMA is a
ivan@140 12 % matrix containing the sparse representations as its columns.
ivan@140 13 %
ivan@140 14 % GAMMA = OMP(D,X,[],T) performs the same operation, but without the
ivan@140 15 % matrix G, using OMP-Cholesky. This call produces the same output as
ivan@140 16 % Batch-OMP, but is significantly slower. Using this syntax is only
ivan@140 17 % recommended when available memory is too small to store G.
ivan@140 18 %
ivan@140 19 % GAMMA = OMP(DtX,G,T) is the fastest implementation of OMP, but also
ivan@140 20 % requires the most memory. Here, DtX stores the projections D'*X. In this
ivan@140 21 % case Batch-OMP is used, but without having to compute D'*X in advance,
ivan@140 22 % which slightly improves runtime. Note that in general, the call
ivan@140 23 %
ivan@140 24 % GAMMA = OMP(D'*X,G,T);
ivan@140 25 %
ivan@140 26 % will be faster than the call
ivan@140 27 %
ivan@140 28 % GAMMA = OMP(D,X,G,T);
ivan@140 29 %
ivan@140 30 % due to optimized matrix multiplications in Matlab. However, when the
ivan@140 31 % entire matrix D'*X cannot be stored in memory, one of the other two
ivan@140 32 % versions can be used. Both compute D'*X for just one signal at a time,
ivan@140 33 % and thus require much less memory.
ivan@140 34 %
ivan@140 35 % GAMMA = OMP(...,PARAM1,VAL1,PARAM2,VAL2,...) specifies additional
ivan@140 36 % parameters for OMP. Available parameters are:
ivan@140 37 %
ivan@140 38 % 'gammamode' - Specifies the representation mode for GAMMA. Can be
ivan@140 39 % either 'full' or 'sparse', corresponding to a full or
ivan@140 40 % sparse matrix, respectively. By default, GAMMA is
ivan@140 41 % returned as a sparse matrix.
ivan@140 42 % 'messages' - Specifies whether progress messages should be displayed.
ivan@140 43 % When positive, this is the number of seconds between
ivan@140 44 % status prints. When negative, indicates that no messages
ivan@140 45 % should be displayed (this is the default).
ivan@140 46 % 'checkdict' - Specifies whether dictionary normalization should be
ivan@140 47 % verified. When set to 'on' (default) the dictionary
ivan@140 48 % atoms are verified to be of unit L2-norm. Setting this
ivan@140 49 % parameter to 'off' disables verification and accelerates
ivan@140 50 % function performance. Note that an unnormalized
ivan@140 51 % dictionary will produce invalid results.
ivan@140 52 % 'profile' - Can be either 'on' or 'off'. When 'on', profiling
ivan@140 53 % information is displayed at the end of the funciton
ivan@140 54 % execution.
ivan@140 55 %
ivan@140 56 %
ivan@140 57 % Summary of OMP versions:
ivan@140 58 %
ivan@140 59 % version | speed | memory
ivan@140 60 % --------------------------------------------------
ivan@140 61 % OMP(DtX,G,T) | very fast | very large
ivan@140 62 % OMP(D,X,G,T) | fast | moderate
ivan@140 63 % OMP(D,X,[],T) | very slow | small
ivan@140 64 % --------------------------------------------------
ivan@140 65 %
ivan@140 66 %
ivan@140 67 % References:
ivan@140 68 % [1] M. Elad, R. Rubinstein, and M. Zibulevsky, "Efficient Implementation
ivan@140 69 % of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit",
ivan@140 70 % Technical Report - CS, Technion, April 2008.
ivan@140 71 %
ivan@140 72 % See also OMP2.
ivan@140 73
ivan@140 74
ivan@140 75 % Ron Rubinstein
ivan@140 76 % Computer Science Department
ivan@140 77 % Technion, Haifa 32000 Israel
ivan@140 78 % ronrubin@cs
ivan@140 79 %
ivan@140 80 % April 2009
ivan@140 81
ivan@140 82
ivan@140 83 % default options
ivan@140 84
ivan@140 85 sparse_gamma = 1;
ivan@140 86 msgdelta = -1;
ivan@140 87 checkdict = 1;
ivan@140 88 profile = 0;
ivan@140 89
ivan@140 90
ivan@140 91 % determine number of parameters
ivan@140 92
ivan@140 93 paramnum = 1;
ivan@140 94 while (paramnum<=nargin && ~ischar(varargin{paramnum}))
ivan@140 95 paramnum = paramnum+1;
ivan@140 96 end
ivan@140 97 paramnum = paramnum-1;
ivan@140 98
ivan@140 99
ivan@140 100 % parse options
ivan@140 101
ivan@140 102 for i = paramnum+1:2:length(varargin)
ivan@140 103 paramname = varargin{i};
ivan@140 104 paramval = varargin{i+1};
ivan@140 105
ivan@140 106 switch lower(paramname)
ivan@140 107
ivan@140 108 case 'gammamode'
ivan@140 109 if (strcmpi(paramval,'sparse'))
ivan@140 110 sparse_gamma = 1;
ivan@140 111 elseif (strcmpi(paramval,'full'))
ivan@140 112 sparse_gamma = 0;
ivan@140 113 else
ivan@140 114 error('Invalid GAMMA mode');
ivan@140 115 end
ivan@140 116
ivan@140 117 case 'messages'
ivan@140 118 msgdelta = paramval;
ivan@140 119
ivan@140 120 case 'checkdict'
ivan@140 121 if (strcmpi(paramval,'on'))
ivan@140 122 checkdict = 1;
ivan@140 123 elseif (strcmpi(paramval,'off'))
ivan@140 124 checkdict = 0;
ivan@140 125 else
ivan@140 126 error('Invalid checkdict option');
ivan@140 127 end
ivan@140 128
ivan@140 129 case 'profile'
ivan@140 130 if (strcmpi(paramval,'on'))
ivan@140 131 profile = 1;
ivan@140 132 elseif (strcmpi(paramval,'off'))
ivan@140 133 profile = 0;
ivan@140 134 else
ivan@140 135 error('Invalid profile mode');
ivan@140 136 end
ivan@140 137
ivan@140 138 otherwise
ivan@140 139 error(['Unknown option: ' paramname]);
ivan@140 140 end
ivan@140 141
ivan@140 142 end
ivan@140 143
ivan@140 144
ivan@140 145 % determine call type
ivan@140 146
ivan@140 147 if (paramnum==3)
ivan@140 148 DtX = varargin{1};
ivan@140 149 G = varargin{2};
ivan@140 150 T = varargin{3};
ivan@140 151 D = [];
ivan@140 152 X = [];
ivan@140 153 elseif (paramnum==4)
ivan@140 154 D = varargin{1};
ivan@140 155 X = varargin{2};
ivan@140 156 G = varargin{3};
ivan@140 157 T = varargin{4};
ivan@140 158 DtX = [];
ivan@140 159 else
ivan@140 160 error('Invalid number of parameters');
ivan@140 161 end
ivan@140 162
ivan@140 163
ivan@140 164 % verify dictionary normalization
ivan@140 165
ivan@140 166 if (checkdict)
ivan@140 167 if (isempty(G))
ivan@140 168 atomnorms = sum(D.*D);
ivan@140 169 else
ivan@140 170 atomnorms = diag(G);
ivan@140 171 end
ivan@140 172 if (any(abs(atomnorms-1) > 1e-2))
ivan@140 173 error('Dictionary columns must be normalized to unit length');
ivan@140 174 end
ivan@140 175 end
ivan@140 176
ivan@140 177
ivan@140 178 % omp
ivan@140 179
ivan@140 180 gamma = ompmexGabor(D,X,DtX,G,T,sparse_gamma,msgdelta,profile);