F24 ECE 551

HW06, Due 11PM Thu. Oct. 17

Pr. 1.

Given an N × N matrix A and initial vector x0 ∈ F N , the power iteration uses the iterative recursion xk+1 = Axk/∥Axk∥2. If A is an N × N Hermitian matrix for which the eigenvalue with the largest magnitude exceed all others, i.e., |λn| < |λ1| , n = 2, . . . , N, then the sequence {xk} generated by the power iteration converges to e ıϕv1 as k → ∞, where v1 is the leading unit-norm eigenvector associated with the largest (in magnitude) eigenvalue λ1, and e ıϕ is an arbitrary phase factor. if v1 ′ x0 = [V ′x0]1 = 0. (Ch. 8 considers more generality.)

(a) Let B denote an N × N Hermitian symmetric matrix with distinct (in magnitude) eigenvalues, ordered such that λN < λN−1 < . . . < λ2 < λ1. Suppose that λ1 is known. Describe how to use one run (where k → ∞) of the power iteration (possibly with a modified input matrix) to compute the eigenvector vN associated with the smallest eigenvalue of B, namely λN , assuming it is unique. Here we mean smallest value, not smallest magnitude. (Do not assume B is invertible.)

Hint. What simple transformation of B maps its smallest eigenvalue to its largest (in magnitude)?

Remember that eigenvalues can be negative so it is possible that |λ1| < |λN |.

(b) Describe a simple way to compute λN from the vN result of part (a). The eigenvector vN is not unique because it could be scaled by e ıϕ. Does that “sign ambiguity” affect your calculation of λN ?

(c) Describe how to modify the scheme to find vN if λ1 is unknown. (You may apply the power iteration more than once in this case, but do not invert B. Use as few applications of the power iteration as possible for full credit.)

Pr. 2.

This problem examines important properties of positive semidefinite and positive definite matrices.

Recall from Ch. 3 that B′B ⪰ 0 for any matrix B.

For each part, you may use results from previous parts if helpful.

(a) (Optional) Show that B′B ≻ 0 if B has full column rank.

(b) (Optional) Show that A ≻ 0 implies A is invertible.

(c) (Optional) Show that A ⪰ 0 and B ⪰ 0 ⇒ A + B ⪰ 0.

(d) Show that A ≻ 0 and B ⪰ 0 ⇒ A + B ≻ 0.

(e) Show that A′A + B′B is invertible if B has full column rank.

(This property is relevant to regularized LS problems.)

(f) Show A′A + B′B is invertible if N (A) ∩ N (B) = {0} , i.e., if A and B have disjoint null spaces other than 0.

(g) (Optional) Show that A ≻ 0, B ≻ 0 ⇒ BAB ≻ 0.

Pr. 3.

In many artificial neural network models used in machine learning, the final layer is often “dense” or “fully connected” and often is affine or linear. This problem focuses on the linear case.

In a supervised learning setting, we are given training data (xn, yn), n = 1, . . . , N consisting of pairs of features xn ∈ RM and responses yn ∈ R. A linear artificial neuron makes a prediction simply by computing the inner product of an input feature x ∈ RM with a (learned) weight vector w ∈ RM, i.e., yˆn = w′xn. We want to train the weight vector w to minimize the average loss over the training data by solving the following optimization problem:

Determine analytically the optimal weight vector wˆ in the case where the loss function is the squared error

You may assume that the data matrix X = [x1 . . . xN] has full row rank. State any conditions needed on N for this assumption (and hence your answer) to be valid.

Hint. You should be able to set this up as a linear least-squares problem and express your answer in terms of the training data feature correlation matrix Kx = N 1 P N n=1 xnx ′ n and the cross-correlation between the training data features and responses Kyx = N 1 P N n=1ynx ′ n .

Pr. 4.

(a) Consider the LLS problem arg minx ∥Ax − y∥ 2 2 . When A has full column rank, the solution is xˆ = (A′A) −1A′y, which involves inverting A′A.

Express the condition number of A′A in terms of the singular values of A.

(b) The Tikhonov regularized solution is arg minx ∥Ax − y∥ 2 2 + β ∥x∥ 2 2 = (A′A + βI) −1A′y. Here we invert a different matrix. Express the condition number of that matrix in terms of the singular values of A and β > 0.

Verify that the regularized solution has a “better” condition number.