KSVD

K-SVD, short for K-Singular Value Decomposition, is a widely used algorithm for dictionary learning and sparse representation of data. It aims to learn a dictionary D whose columns (atoms) enable a set of training signals Y to be represented as Y ≈ D X with sparse coefficient vectors X. The standard formulation constrains D to have unit-norm columns and seeks a sparse X that minimizes reconstruction error.

The method proceeds by alternating between sparse coding and dictionary update. With the dictionary D fixed, KSVD computes sparse representations X for all signals, typically using a pursuit algorithm such as Orthogonal Matching Pursuit (OMP) with a prescribed sparsity level. This step yields a sparse coefficient matrix X that encodes which atoms are used for each training sample.

In the dictionary update step, KSVD updates one atom at a time. For each atom k, it identifies the subset of training signals that use that atom (nonzero coefficients in row k of X). It then computes the residual matrix E_k by removing the contribution of all other atoms from those signals. A rank-1 approximation of E_k is obtained via singular value decomposition, and the leading left singular vector becomes the new atom d_k. The corresponding coefficients in X are updated accordingly to reflect the new atom and its singular value.

KSVD iterates these steps until convergence or a maximum number of iterations is reached. It has been applied to image denoising and restoration, compression, inpainting, and various signal processing tasks, and serves as a foundational approach in many sparse coding pipelines.