Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Sparse image compression

In sparse image compression, we are given the pixel representation of a ‘‘target’’ image, as a vector in mathbf{R}^m. We would like to represent the image as a linear combination of ‘‘basic’’ images a_j, j=1,ldots,n, where the matrix A=[a_1,ldots,a_n] in mathbf{R}^{m times n} is called the dictionary.

Thus, we would like to find coefficients x_j, j=1,ldots,n such that

y = sum_{j=1}^n x_j a_j,

or, more compactly, y = Ax.

Assuming the above equation has solutions, we are interested in finding one solution x in mathbf{R}^n with the largest number of zeros. This is (empirically) achieved with solving a minimum-norm problem of the form

min_x : |x|_1 ~:~ Ax = y,

Once a sparse representation of the image is found, we can (say) send the image over the internet by sending only the (few) non-zero coefficients x_j and their corresponding indices j. The recipient of these coefficients can reconstruct the image via y=Ax. This approach assumes that the dictionary is available to both source and recipient.