Uniformly smooth space

From formulasearchengine
Jump to navigation Jump to search

Template:No footnotes

Template:Orphan

In applied mathematics, K-SVD is an algorithm of deciding dictionary of sparse representation in a singular value decomposition approach. K-SVD is a generalization of the k-means clustering method, iteratively alternates between sparse coding coefficient of the example based on current dictionary and atoms in the dictionary. The update of dictionary enables K-SVD algorithm to better fit the data. K-SVD can be found widely use in applications such as image processing, audio processing, biology, and document analysis.

Sparsity description

Given an overcomplete dictionary matrix Dn×K that contains K signal-atoms for each columns, a signal yn can be represented as a linear combination of these atoms. To represent y, the sparse representation x should satisfy the exact condition y=Dx, or approximate condition yDx, or yDxpϵ. The vector xK contains the representation coefficients of the signal y. Typically, norm p is selected as 1,2, or .

If n<K and D is a full-rank matrix, an infinite number of solutions are available for the representation problem, Hence, constraints should be set on the solution. Also, to ensure sparsity, the solution with the fewest number of nonzero coefficients is preferred. Thus, the sparsity representation is the solution of either

(P0)min\limits xx0subject to y=Dx

or

(P0,ϵ)min\limits xx0subject to yDx2ϵ

where the L0 norm counts the nonzero entries of a vector. Please see Matrix norm.

Choice of dictionary

  • Generalize the K-means:

The k-means clustering can be also regarded as a method of sparse representation. That is, finding the best possible codebook to represent the data samples {yi}i=1M by nearest neighbor, by solving

min\limits D,X{YDXF2}subject to i,xi=ek for some k.

or can be written as

min\limits D,X{YDXF2}subject to i,xi0=1.

The sparse representation term xi=ek enforces K-means algorithm to use only one atom (column) in dictionary D. To relax this constraint, target of the K-SVD algorithm is to represent signal as a linear combination of atoms in D.

The K-SVD algorithm follows the construction flow of K-means algorithm. However, In contrary to K-means, in order to achieve linear combination of atoms in D, sparsity term of the constrain is relaxed so that nonzero entries of each column xi can be more than 1, but less than a number L0.

So, the objective function becomes

min\limits D,X{YDXF2}subject to i,xi0T0.

or in another objective form

min\limits D,Xixi0subject to i,YDXF2ϵ.

In the K-SVD algorithm, the D is first to be fixed and the best coefficient matrix X. As finding the truly optimal X is impossible, we use an approximation pursuit method. Any such algorithm as OMP, the orthogonal matching pursuit in can be used for the calculation of the coefficients, as long as it can supply a solution with a fixed and predetermined number of nonzero entries T0.

After the sparse coding task, the next is to search for a better dictionary D. However, finding the whole dictionary all at a time is impossible, so the process then update only one column of the dictionary D each time while fix X. The update of kthis done by rewriting the penalty term as

YDXF2=|Yj=1KdjxTj|F2=|(YjkdjxTj)dkxTk)|F2=EkdkxTkF2

where xTk denotes the k-th row of X.

By decomposing the multiplication DX into sum of K rank 1 matrices, we can assume the other K1 terms are assumed fixed, and the kth remains unknown. After this step, we can solve the minimization problem by approximate the Ek term with a rank1 matrix using singular value decomposition, then update dk with it. However, the new solution of vector xTk is very likely to be filled, because the sparsity constrain is not enforced.

To cure this problem, Define ωk as

ωk={i1iN,xTk(i)0}.

Which points to examples {yi} that use atom dk (also the entries of xi that is nonzero). Then, define Ωk as a matrix of size N×|ωk|, with ones on the (i-th,ωk(i)) entries and zeros otherwise. When multiplying xRk=xTkΩk, this shrinks the row vector xTk by discarding the nonzero entries. Similarly, the multiplication YkR=YΩk is the subset of the examples that are current using the dk atom. The same effect can be seen on EkR=EkΩk.

So the minimization problem as mentioned before becomes

EkΩkdkxTkΩkF2=EkRdkxRkF2

and can be done by directly using SVD. SVD decomposes EkR into UΔVT. The solution for dk is the first column of U, the coefficient vector xRk as the first column of V×Δ(1,1). After updated the whole dictionary, the process then turns to iteratively solve X, then iteratively solve D.

See also

References