Convex Optimization

Matlab Assignment

Problem 1. Let the set S be described by,

.

• Use Matlab to draw the set S and investigate its convexity.
• Show your conclusion in part (a) theoretically.

Problem 2. Let Q₁ and Q₂ be arbitrary n n symmetric matrices (n > 2).

• Use Matlab to draw the set and investigate its convexity.
• Extra point: Can you show your conclusion in part (a) theoretically?

Problem 3. Let A be a real mn matrix with a singular value decomposition given by A = UV ^T (as discussed in class). For a positive integer k min{m,n}, we let A_k denote an m n matrix which is an

approximation of the matrix A obtained from its top k singular values and singular vectors, i.e.,

Ak = UkkVkT,

where U_k has the first k columns of U, V_k has the first k columns of V , and _k is the upper left k k block of .

• To provide a good approximation for A, consider the cost function kA Xk₂ where X is restricted to be an m n matrix with rank(X) k. It can be shown that A_k is the minimizer of the cost function kA Xk₂. Download the file HajiFirouz.jpg. Read this file in Matlab by typing:

A=imread(HajiFirouz.jpg); A=im2double(A) ;

A=rgb2gray(A) ;

Figure 1: Haji Firouz in Problem 8

The result is a 395 665 matrix A, with each entry representing a single pixel in the picture with a number between 0 and 1.

For different values of k, use Matlab to compute A_k, construct a compressed image with A_k (You can used the command imwrite), and report the value of kA A_kk₂.

• Based on your experiments in part (a), provide a good compressed image for HajiFirouz and explain your interpretations.

References

[1] Boyd, Stephen, Stephen P. Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

2