3
$\begingroup$

Given Lemma 1, I want to prove the following corollary.

lemma 1 (Rayleigh Quotient): Given matrix $A \succeq 0$, \begin{equation} \lambda_{\min} (A) = \min_{x \in \mathbb R^n}\frac{x^\top A x}{x^\top x}. \end{equation}

Corollary: Given matrix $A \succeq 0$, \begin{equation} \lambda_{\min}(A) = \underset{U \in \Delta_{n \times n}}{\min} \langle A,U \rangle. \end{equation} where $\Delta_{n \times n} \overset{\operatorname{def}}{=} \{M \in \mathbb R^{n \times n}~:~M \succeq 0,~\mathrm{Trace}(M) = 1 \}$, and $\langle X, Y\rangle = \mathrm{Trace}(XY)$ denotes the inner product between two symmetric matrices.

I found the following proof in the net, but I cannot totally understand it.

Proof: Let \begin{equation*} U^* = \underset{U \in \Delta_{n \times n}}{\arg\min} \langle A, U\rangle. \end{equation*} We take the SVD $A = \sum_{i=1}^{n} \lambda_i u_i u_i^\top$ and $\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$. It is clear that $\langle A, U^* \rangle \leq \langle A, u_1 u_1^\top \rangle$ $= \lambda_{\min}(A)$. Next, we need to show $\lambda_{\min}(A) \leq \langle A, U^* \rangle$.

The SVD of $U^* = \sum_{i=1}^{n} \sigma_i v_i v_i^\top$. If $\lambda_{\min}(A) > \langle A, U^* \rangle$, then $\lambda_{\min}(A) > \sum_{i=1}^{n} \sigma_i v_i^\top A v_i$. Since $\sum \sigma_i = 1$, there exists $k$ such that $\lambda_{\min}(A) > v_k^\top A v_k$ which contradicts Lemma 1.

The parts of the proof I do not understand well are:

  • Why $\langle A, U^* \rangle \leq \langle A, u_1 u_1^\top \rangle$ is clear?
  • Why?

there exists $k$ such that $\lambda_{\min}(A) > v_k^\top A v_k$ which contradicts Lemma 1

I will be very grateful if you could help me to understand these parts.

$\endgroup$

1 Answer 1

3
$\begingroup$

The first inequality follows because $u_1 u_1^{\mathsf{T}} \in \Delta_{n \times n}$, and $U^{\ast}$ is the minimizer over that set:

$$ \langle U^{\ast}, A \rangle = \min_{U \in \Delta_{n \times n}} \langle U, A \rangle \leq \langle u_1 u_1^{\mathsf{T}}, A \rangle. $$

Indeed, you can verify that $u_1 u_1^{\mathsf{T}} \succeq 0$ and its trace is equal to $$ \mathsf{tr}(u_1 u_1^{\mathsf{T}}) = \mathsf{tr}(u_1^{\mathsf{T}} u_1) = \|u_1\|^2 = 1. $$

The second part follows because $$ \sum_{i = 1}^n \sigma_i v_i^{\mathsf{T}} A v_i \geq \underbrace{\left( \sum_{i = 1}^n \sigma_i \right)}_{= 1} \cdot \min_{i = 1, \dots, n} \left( v_i^{\mathsf{T}} A v_i \right). $$

In particular, the minimum is attained for some index $k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .