[Math] Show That Minimizer of Rayleigh Quotient Is the Smallest Eigenvalue – $ \min_{x : \left\| x \right\| = 1} {x}^{*} {A}^{*} A x = {\lambda}_{1}^{2} $

convex-analysiseigenvalues-eigenvectorslinear algebraoptimization

Show that (Some form of Rayleigh Quotient):

$$ \min_{x : \left\| x \right\| = 1} {x}^{*} {A}^{*} A x = {\lambda}_{1}^{2} $$

Where $ {\lambda}_{1} $ is the smallest singular value of $ A \in \mathbb{C}^{n \times n}$.

My attempt:

Let us define $ B = {A}^{*} A $, and say that $ \left( x, {\lambda}_{i}^{2} \right) $ is an eigen-pair of $ B $, i.e., $ B x = {\lambda}_{i}^{2} x $, such that the objective of the above optimization problem can be expressed as

\begin{align}
{x}^{*} \underbrace{B x}_{ ={\lambda}_{i}^{2} x } = {x}^{*} {\lambda}_{i}^{2} {x} = {\lambda}_{i}^{2} \hspace{-16mm}\underbrace{ {\left\| x \right\|}^{2} }_{\hspace{19mm}=1 \\ \text{due to the constraint that } \left\| x \right\|=1} = {\lambda}_{i}^{2}.
\end{align}

Also, $ B $ is Hermitian. So, the eigenvalues of $ B $ are non-negative and real-valued. Thus, the minimization problem boils down to the search over the minimum eigenvalue $ \min \{ {\lambda}_{i}^{2} \} $ which will render the smallest eigenvalue that can be said as $ {\lambda}_{1}^{2} $.

Do you experts agree with this approach?

Can this be solved in some other ways, e.g., classical Lagrange multiplier based?

Thank you so much in advance.

Best Answer

I will sketch 2 approaches for the solution.

Option I

  1. Write the Lagrange of the problem and show that the dual variable must be an eigenvalue.
  2. Show that the Eigenvector of the Eigenvalue achieves the minimum value and hence the problem is solved.

Option II

Define $ B = {A}^{T} A $ which is PSD which means it has Eigen Decomposition $ B = {V}^{T} D V $ where $ V $ is Unitary matrix and $ D $ is diagonal matrix.

So the problem:

$$\begin{align*} \min_{x} \quad & {x}^{T} B x \\ \text{subject to} \quad & \left\| x \right\| = 1 \end{align*}$$

Becomes:

$$\begin{align*} \min_{x} \quad & {y}^{T} D y \\ \text{subject to} \quad & \left\| y \right\| = 1 \end{align*}$$

Where $ y = V x $.
Since $ V $ is Unitary which preserves $ {L}_{2} $ norm the constraint $ \left\| y \right\| = 1 $ is equivalent of $ \left\| x \right\| = 1 $.

Now, if you think about it, $ x $ like selecting and weighing columns of $ V $.
It is only logical it will select the column which matches the lowest value of $ D $ which is exactly the pair of Eigenvector and the smallest Eigenvalue.

Related Question