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

Exercises

SVD > Exercises

SVD of simple matrices

  1. Consider the matrix

A = left( begin{array}{ccc} 1 & 0 & 00 &-2&00&0&00&0&0 end{array}right).

    1. Find the range, nullspace, and rank of A.

    2. Find an SVD of A.

    3. Determine the set of solutions to the linear equation Ax = y, with

y = left( begin{array}{c}2300end{array}right), ;; y = left( begin{array}{c}2003end{array}right).

  1. Consider the 2 times 2 matrix

A = frac{1}{sqrt{10}} left( begin{array}{c} 2 1 end{array}right) left( begin{array}{cc}1&-1 end{array}right) + frac{2}{sqrt{10}} left( begin{array}{c}-1 2 end{array}right) left( begin{array}{cc}1&1 end{array}right).

    1. What is an SVD of A? Express it as A = U S V^T, with S the diagonal matrix of singular values ordered in decreasing fashion. Make sure to check all the properties required for U,S,V.

    2. Find the semi-axis lengths and principal axes (minimum and maximum distance and associated directions from mathbf{E} to the center) of the ellipsoid

mathbf{E}(A) = left{ Ax ~: x in mathbf{R}^2 , ;; |x|_2 le 1 right}.

Hint: Use the SVD of A to show that every element of {cal E}(A) is of the form y = Ubar{y} for some element bar{y} in {cal E}(S). That is, {cal E}(A) = { Ubar{y} ::: bar{y} in {cal E}(S) }. (In other words the matrix U maps {cal E}(S) into the set {cal E}(A).) Then analyze the geometry of the simpler set {cal E}(S).

    1. What is the set {cal E}(A) when we append a zero vector after the last column of A, that is A is replaced with tilde{A} = (A,0) in mathbf{R}^{2 times 3}?

    2. Same question when we append a row after the last row of A, that is, A is replaced with tilde{A} = [A^T,0]^T in mathbf{R}^{3 times 2}. Interpret geometrically your result.

Rank and SVD

alt text 

The image on the left shows a 256 times 256 matrix A of pixel values. The lines indicate +1 values; at each intersection of lines the corresponding matrix element is +2. All the other elements are zero.

  1. Show that for some permutation matrices P,Q, the permuted matrix B:=PAQ has the symmetric form B = pq^T+qp^T, for two vectors p,q. Determine P,Q,B and p,q.

  2. What is the rank of A? Hint: find the nullspace of B.

  3. Find an SVD of A. Hint: Find an eigenvalue decomposition of S, using the results of an exercise on eigenvalue here.

Procrustes problem

The Orthogonal Procrustes problem is a problem of the form

min_{X} : |AX-B|_F ~:~ X^TX = I_p,

where |cdot|_F denotes the Frobenius norm, and the matrices A in mathbf{R}^{m times n}, B in mathbf{R}^{m times p} are given. Here, the matrix variable X in mathbf{R}^{n times p} is constrained to have orthonormal columns. When n=m=p, the problem can be interpreted geometrically as seeking a transformation of points (contained in A) to other points (contained in B) that involves only rotation.

  1. Show that the solution of the Procrustes problem above can be found via the SVD of the matrix A^TB.

  2. Derive a formula for the answer to the constrained least-squares problem

min_x : |Ax-b|_2 ~:~ |x|_2 = 1,

with A in mathbf{R}^{m times n}, b in mathbf{R}^m given.

SVD and projections

  1. We consider a set of m data points x_i in mathbf{R}^n, i=1,ldots,m. We seek to find a line in mathbf{R}^n such that the sum of the squares of the distances from the points to the line is minimized. To simplify, we assume that the line goes through the origin.

    1. Consider a line that goes through the origin {cal L} : = { t u ::: t in mathbf{R}}, where u in mathbf{R}^n is given. (You can assume without loss of generality that |u|_2 = 1.) Find an expression for the projection of a given point x on {cal L}.

    2. Now consider the m points and find an expression for the sum of the squares of the distances from the points to the line {cal L}.

    3. Explain how you would find the line via the SVD of the n times m matrix X = [x_1,ldots,x_m].

    4. How would you address the problem without the restriction that the line has to pass through the origin?

  2. Solve the same problems as previously by replacing the line by an hyperplane.

SVD and least-squares

  1. Consider the matrix A formed as A=(c_1,c_2,c_3), with

c_1 = (1,2,8), ;; c_2 = (3,6,9), ;; c_3 = c_1-4c_2 + epsilon_1 v, ;; epsilon_1 = .0000001,

with v a vector chosen randomly in [-1/2,1/2]^4. In addition we define

y = 2c_1 - 7c_2 + epsilon_2 w, ;; epsilon_2 = .0001,

with again w chosen randomly in [-1/2,1/2]^4. We consider the associated least-squares problem

min_x : |Ax-y|_2 .

    1. What is the rank of A?

    2. Apply the least-squares formula x^ast = (A^TA)^{-1}A^Ty. What is the norm of the residual vector, r = Ax-y?

    3. Express the least-squares solution in terms of the SVD of A. That is, form the pseudo-inverse of A and apply the formula x^ast = A^dagger y. What is now the norm of the residual?

    4. Interpret your results.

  2. Consider a least-squares problem

min_x : |Ax-y|_2

where the data matrix A in mathbf{R}^{m times n} has rank one.

    1. Is the solution unique?

    2. Show how to reduce the problem to one involving one scalar variable.

    3. Express the set of solutions in closed-form.