SVD decomposition

Question

Let $P$ be a $n\times 1$ vector and $A$ be an $m\times n$ matrix.

Prove that the smallest eigenvalue of $A^TA$ is the solution to the minimizing $P^TA^TAP$ S.T. $P^TP=1$.

I have used SVD to declare $A=UDV^T$, where U is unitary and D is diagonal.

$$A^TA=(UDV^T)^TUDV^T=(DV^T)^TU^TUDV^T=(DV^T)^TDV^T=VD^TDV^T=VD^2V^T$$ Hence: $A^TAV=VD^2V^TV=VD^2$ and for $\lambda=D^2$ $V$ is eigen vector of $A^TA$.

Let us denote $\lambda_1$ as the smallest eigenvalue of $A^TA$, $$P^TA^TAP=P^T(A^TAP)=P^T(\lambda_1P)=\lambda_1$$

Why is this transition correct: $P^T(A^TAP)=P^T(\lambda_1P)$? Can I simply substitute $A^TA$ by the smallest eigenvalue or is it becaus of the minimalization?

Answer 1

Note that $P^TVD^2V^TP$ can be written as $Q^TD^2Q$ where $Q = V^TP$, and that the entries of $D^2$ are the eigenvalues of $A^TA$. Note also that $Q^TQ = P^TP = 1$. Writing $Q = [q_1,\dots,q_n]^T$, we have $$ Q^TD^2Q = \sum_{i=1}^n \lambda_i q_i^2 \leq \sum_{i=1}^n \lambda_1 q_i^2 = \lambda_1 $$

Answer 2

I think there are things to be fixed.

Firstly, $D^TD \neq D^2$, as $D$ is a $m\times n$ matrix. Secondly, for $m,n>1$, $D^2$ is not a number, but rather a matrix. Therefore, it cannot be an eigenvalue.

Also, I suppose that $P$ is $n\times 1$. As $P^TA^TAP$ is a function of the vector variable $P$, in order to minimise it, we can use Lagrange multipliers methods, with the constraint $P^TP=1$.

$F=P^TA^TAP-\lambda (P^TP-1)$

The derivative is

$2P^TA^TA-2\lambda P^T=0 \implies P^TA^TA-\lambda P^T=0$

Further simplification results in

$P^TA^TA-\lambda P^T=0 \implies A^TA-\lambda I=0 \implies (A^TA-\lambda I)P=0$

As $P\neq 0$, we need to have $A^TA-\lambda I$ to be singular. We have it singular if and only if $\lambda$ is an eigenvalue of $A^TA$. For each $\lambda$ there must be a $P$ in the null-space of $A^TA-\lambda I$, such that $(A^TA-\lambda I)P=0$. Therefore, we have pairs of $(\lambda,P)$ that are local extrema. Now, if one writes the last result as

$(A^TA-\lambda I)P=0 \implies A^TAP=\lambda P \implies P^TA^TAP=\lambda P^TP=\lambda$

then it is obvious that the minimum of $P^TA^TAP$ is achieved for the smallest lambda. However, the last thing to check is to see if the function that is being minimised is convex, so we can have the local minimum as a global minimum. The Hessian matrix is $A^TA-\lambda I$ and for $\lambda$ being the minimum eigenvalue it is definitely positive semi-definite and, consequently, convex.