Help explain an equality why $\max_i \{ 1-\alpha \lambda_i\} = |\max \{1-\alpha \lambda_1, 1-\alpha\lambda_n\}| $, circled in the following and why $\alpha = \frac{2}{\lambda_n + \lambda_1}$. Thanks!

I summarize it as the following. $A$ is symmetric, and $\lambda_1 \le ... \le \lambda_n$ are its eigenvalues (all real) in ascending order. We want to minimize $\|I-\alpha A\|_2$, since it is spectral norm of a symmetric matrix, then $\|I-\alpha A\|_2 = \max_i |1-\alpha \lambda_i| $.

What I can see is $\max_i |1-\alpha \lambda_i|=\max \{ |1-\alpha \lambda_1|,|1-\alpha \lambda_n|\}$. I cannot see why the following circled part holds. Am I missing something here?

enter image description here enter image description here


For each $1\leq i\leq n,$ let $z_{i}=1-\alpha\lambda_{i}.$ Note that when $\alpha<0,$ $\lambda_{i}\mapsto z_{i}$ is order-preserving, and when $\alpha\geq 0,$ $\lambda_{i}\mapsto z_{i}$ is order-reversing. In either case, this leaves $\min\{z_{1},z_{n}\}\leq z_{i}\leq\max\{z_{1},z_{n}\}$ for all $1\leq i\leq n,$ so $$-\max\{|z_{1}|,|z_{n}|\}\leq\min\{z_{1},z_{n}\}\leq z_{i}\leq \max\{z_{1},z_{n}\}\leq\max\{|z_{1}|,|z_{n}|\},$$ which gives $|z_{i}|\leq\max\{|z_{1}|,|z_{n}|\}$ for all $1\leq i\leq n,$ and thus for the maximum over $i$ in this range.

However, the statement $\max_{i}|z_{i}|\leq|\max\{z_{1},z_{n}\}|$ is false generally: Let $\{\lambda_{1},\lambda_{2},\lambda_{3}\}=\{1,2,3\}.$ Then $\max\{1-(1)1,1-(1)2,1-(1)3\}=\max\{0,-1,-2\}=0,$ but $\max_{i}|z_{i}|=2$ for this example, with $\alpha=1.$

The minimizer of $\max\{|1-\alpha\lambda_{1}|,|1-\alpha\lambda_{n}|\}$ with respect to $\alpha$ is then given by $2/(\lambda_{1}+\lambda_{n}),$ as claimed.

  • $\begingroup$ Thanks! Can I ask why the minimizer of $\max\{|1-\alpha\lambda_{1}|,|1-\alpha\lambda_{n}|\}$ is $2/(\lambda_{1}+\lambda_{n})$? Thanks! $\endgroup$ – River Oct 9 '17 at 15:00
  • $\begingroup$ If $\alpha$ is close to $\lambda_{1}^{-1},$ the right term is larger, and if $\alpha$ is close to $\lambda_{n}^{-1},$ the left term is larger. This value of $\alpha$ makes both terms equal (this is admittedly a hand-wavy explanation). $\endgroup$ – RideTheWavelet Oct 9 '17 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.