World Library  
Flag as Inappropriate
Email this Article

Rayleigh quotient

Article Id: WHEBN0000306343
Reproduction Date:

Title: Rayleigh quotient  
Author: World Heritage Encyclopedia
Language: English
Subject: Spectral theory, Rayleigh, Canonical correlation, Expander graph, Compact operator on Hilbert space
Collection: Linear Algebra
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Rayleigh quotient

In mathematics, for a given complex Hermitian matrix M and nonzero vector x, the Rayleigh quotient[1] R(M, x), is defined as:[2][3]

R(M,x) := {x^{*} M x \over x^{*} x}.

For real matrices and vectors, the condition of being Hermitian reduces to that of being symmetric, and the conjugate transpose x^{*} to the usual transpose x'. Note that R(M, c x) = R(M,x) for any non-zero real scalar c. Recall that a Hermitian (or real symmetric) matrix has real eigenvalues. It can be shown that, for a given matrix, the Rayleigh quotient reaches its minimum value \lambda_\min (the smallest eigenvalue of M) when x is v_\min (the corresponding eigenvector). Similarly, R(M, x) \leq \lambda_\max and R(M, v_\max) = \lambda_\max.

The Rayleigh quotient is used in the min-max theorem to get exact values of all eigenvalues. It is also used in eigenvalue algorithms to obtain an eigenvalue approximation from an eigenvector approximation. Specifically, this is the basis for Rayleigh quotient iteration.

The range of the Rayleigh quotient (for matrix that is not necessarily Hermitian) is called a numerical range, (or spectrum in functional analysis). When the matrix is Hermitian, the numerical range is equal to the spectral norm. Still in functional analysis, \lambda_\max is known as the spectral radius. In the context of C*-algebras or algebraic quantum mechanics, the function that to M associates the Rayleigh-Ritz quotient R(M,x) for a fixed x and M varying through the algebra would be referred to as "vector state" of the algebra.

Contents

  • Bounds for Hermitian M 1
  • Special case of covariance matrices 2
    • Formulation using Lagrange multipliers 2.1
  • Use in Sturm–Liouville theory 3
  • Generalizations 4
  • See also 5
  • References 6
  • Further reading 7

Bounds for Hermitian M

As stated in the introduction, it is R(M,x) \in \left[\lambda_\min, \lambda_\max \right]. This is immediate after observing that the Rayleigh quotient is a weighted average of eigenvalues of M:

R(M,x) = {x^{*} M x \over x^{*} x} = \frac{\sum_{i=1}^n \lambda_i y_i^2}{\sum_{i=1}^n y_i^2}

where (\lambda_i, v_i) is the ith eigenpair after orthonormalization and y_i = v_i^* x is the ith coordinate of x in the eigenbasis. It is then easy to verify that the bounds are attained at the corresponding eigenvectors v_\min, v_\max.

The fact that the quotient is a weighted average of the eigenvalues can be used to identify the second, the third, ... largest eigenvalues. Let \lambda_{max} = \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_n = \lambda_{min} be the eigenvalues in decreasing order. If x is constrained to be orthogonal to v_1, in which case y_1 = v_1^*x = 0 , then R(M,x) has the maximum \lambda_2, which is achieved when x = v_2.

Special case of covariance matrices

An empirical covariance matrix M can be represented as the product A' A of the data matrix A pre-multiplied by its transpose A'. Being a positive semi-definite matrix, M has non-negative eigenvalues, and orthogonal (or othogonalisable) eigenvectors, which can be demonstrated as follows.

Firstly, that the eigenvalues \lambda_i are non-negative:

M v_i = A' A v_i = \lambda_i v_i
\Rightarrow v_i' A' A v_i = v_i' \lambda_i v_i
\Rightarrow \left\| A v_i \right\|^2 = \lambda_i \left\| v_i \right\|^2
\Rightarrow \lambda_i = \frac{\left\| A v_i \right\|^2}{\left\| v_i \right\|^2} \geq 0.

Secondly, that the eigenvectors vi are orthogonal to one another:

\begin{align} &\qquad \qquad M v_i = \lambda _i v_i \\ &\Rightarrow v_j' M v_i = \lambda _i v_j' v_i \\ &\Rightarrow \left (M v_j \right )' v_i = \lambda _j v_j' v_i \\ &\Rightarrow \lambda_j v_j ' v_i = \lambda _i v_j' v_i \\ &\Rightarrow \left (\lambda_j - \lambda_i \right ) v_j ' v_i = 0 \\ &\Rightarrow v_j ' v_i = 0 \end{align}

If the eigenvalues are different – in the case of multiplicity, the basis can be orthogonalized.

To now establish that the Rayleigh quotient is maximised by the eigenvector with the largest eigenvalue, consider decomposing an arbitrary vector x on the basis of the eigenvectors vi:

x = \sum _{i=1} ^n \alpha _i v_i,

where

\alpha_i = \frac{x'v_i}{v_i'v_i} = \frac{\langle x,v_i\rangle}{\left\| v_i \right\| ^2}

is the coordinate of x orthogonally projected onto vi. Therefore we have:

R(M,x) = \frac{x' A' A x}{x' x} = \frac{ \left (\sum _{j=1} ^n \alpha _j v_j \right )' \left ( A' A \right ) \left (\sum _{i=1} ^n \alpha _i v_i \right )}{ \left (\sum _{j=1} ^n \alpha _j v_j \right )' \left (\sum _{i=1} ^n \alpha _i v_i \right )}

which, by orthogonality of the eigenvectors, becomes:

R(M,x) = \frac{\sum _{i=1} ^n \alpha_i^2 \lambda _i}{\sum _{i=1} ^n \alpha_i^2} = \sum_{i=1}^n \lambda_i \frac{(x'v_i)^2}{ (x'x)( v_i' v_i)}

The last representation establishes that the Rayleigh quotient is the sum of the squared cosines of the angles formed by the vector x and each eigenvector vi, weighted by corresponding eigenvalues.

If a vector x maximizes R(M,x), then any non-zero scalar multiple kx also maximizes R, so the problem can be reduced to the Lagrange problem of maximizing \sum _{i=1}^n \alpha_i^2 \lambda _i under the constraint that \sum _{i=1} ^n \alpha _i ^2 = 1.

Define: βi = α2
i
. This then becomes a linear program, which always attains its maximum at one of the corners of the domain. A maximum point will have \alpha_1 = \pm 1 and \alpha _i = 0 for all i > 1 (when the eigenvalues are ordered by decreasing magnitude).

Thus, as advertised, the Rayleigh quotient is maximised by the eigenvector with the largest eigenvalue.

Formulation using Lagrange multipliers

Alternatively, this result can be arrived at by the method of Lagrange multipliers. The problem is to find the critical points of the function

R(M,x) = x^T M x ,

subject to the constraint \|x\|^2 = x^Tx = 1. I.e. to find the critical points of

\mathcal{L}(x) = x^T M x -\lambda \left (x^Tx - 1 \right),

where λ is a Lagrange multiplier. The stationary points of \mathcal{L}(x) occur at

\frac{d\mathcal{L}(x)}{dx} = 0
\therefore 2x^T M^T - 2\lambda x^T = 0
\therefore M x = \lambda x

and

R(M,x) = \frac{x^T M x}{x^T x} = \lambda \frac{x^Tx}{x^T x} = \lambda.

Therefore, the eigenvectors x_1, \cdots, x_n of M are the critical points of the Rayleigh Quotient and their corresponding eigenvalues \lambda_1, \cdots, \lambda_n are the stationary values of R.

This property is the basis for principal components analysis and canonical correlation.

Use in Sturm–Liouville theory

Sturm–Liouville theory concerns the action of the linear operator

L(y) = \frac{1}{w(x)}\left(-\frac{d}{dx}\left[p(x)\frac{dy}{dx}\right] + q(x)y\right)

on the inner product space defined by

\langle{y_1,y_2}\rangle = \int_a^b w(x)y_1(x)y_2(x) \, dx

of functions satisfying some specified boundary conditions at a and b. In this case the Rayleigh quotient is

\frac{\langle{y,Ly}\rangle}{\langle{y,y}\rangle} = \frac{\int_a^b y(x)\left(-\frac{d}{dx}\left[p(x)\frac{dy}{dx}\right] + q(x)y(x)\right)dx}{\int_a^b{w(x)y(x)^2}dx}.

This is sometimes presented in an equivalent form, obtained by separating the integral in the numerator and using integration by parts:

\begin{align} \frac{\langle{y,Ly}\rangle}{\langle{y,y}\rangle} &= \frac{ \left \{ \int_a^b y(x)\left(-\frac{d}{dx}\left[p(x)y'(x)\right]\right) dx \right \}+ \left \{\int_a^b{q(x)y(x)^2} \, dx \right \}}{\int_a^b{w(x)y(x)^2} \, dx} \\ &= \frac{ \left \{\left. -y(x)\left[p(x)y'(x)\right] \right |_a^b \right \} + \left \{\int_a^b y'(x)\left[p(x)y'(x)\right] \, dx \right \} + \left \{\int_a^b{q(x)y(x)^2} \, dx \right \}}{\int_a^b w(x)y(x)^2 \, dx}\\ &= \frac{ \left \{ \left. -p(x)y(x)y'(x) \right |_a^b \right \} + \left \{ \int_a^b \left [p(x)y'(x)^2 + q(x)y(x)^2 \right] \, dx \right \} } {\int_a^b{w(x)y(x)^2} \, dx}. \end{align}

Generalizations

  1. For a given pair (A, B) of matrices, and a given non-zero vector x, the generalized Rayleigh quotient is defined as:
    R(A,B; x) := \frac{x^* A x}{x^* B x}.
    The Generalized Rayleigh Quotient can be reduced to the Rayleigh Quotient R(D, C^*x) through the transformation D = C^{-1} A {C^*}^{-1} where CC^* is the Cholesky decomposition of the Hermitian positive-definite matrix B.
  2. For a given pair (x, y) of non-zero vectors, and a given Hermitian matrix H, the generalized Rayleigh quotient can be defined as:
    R(H; x,y) := \frac{y^* H x}\sqrt{y^*y \cdot x^*x}
    which coincides with R(H,x) when x=y.

See also

References

  1. ^ Also known as the Rayleigh–Ritz ratio; named after Walther Ritz and Lord Rayleigh.
  2. ^ Horn, R. A. and C. A. Johnson. 1985. Matrix Analysis. Cambridge University Press. pp. 176–180.
  3. ^ Parlet B. N. The symmetric eigenvalue problem, SIAM, Classics in Applied Mathematics,1998

Further reading

  • Shi Yu, Léon-Charles Tranchevent, Bart Moor, Yves Moreau, Kernel-based Data Fusion for Machine Learning: Methods and Applications in Bioinformatics and Text Mining, Ch. 2, Springer, 2011.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.