Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I have a quadratic form $\mathbf{x}^T A \mathbf{x}$ (where $A\in \mathbb{R}^{n\times n}$ is symmetric matrix and $\mathbf{x}\in \mathbb{R}^n$) that I want to minimize given the normalization constraint $\mathbf{x}^T\mathbf{x}=1$.

Because $\mathbf{A}$ is a adjacency matrix of an undirected graph then I know that it is symmetric and real and also sparse.

What is an appropriate memory conservative algorithm to solve this kind of problem?

Is it good to solve the eigensystem $\mathbf{A}\mathbf{x}=\lambda \mathbf{x}$ and then taking as solution the first smallest nonzero eigenvalue and its related eigenvector?

If this is the way to proceed how is it possible to get the smallest eigenvalue with subspace iteration?

share|improve this question
    
Well, $\mathbf x=0$ can't possibly be a solution because it doesn't satisfy $\|\mathbf x\|=1$. That doesn't exclude that $A$ has a zero eigenvalue, though. –  Wolfgang Bangerth Oct 30 '12 at 2:54

2 Answers 2

The optimal objective function value will be the minimal eigenvalue of $\mathbf{A}$, including zero eigenvalues, and the optimal solution will be the eigenvector of $\mathbf{A}$ corresponding to that eigenvalue.

Eigenvectors, by definition, must be nonzero vectors.

One way to derive this answer is to note that a symmetric matrix $\mathbf{A}$ will always have the eigendecomposition $\mathbf{A}$ = $\mathbf{Q}^{T}\boldsymbol{\Lambda}\mathbf{Q}$, where $\mathbf{Q}$ is an orthogonal matrix and $\boldsymbol{\Lambda}$ is a diagonal matrix consisting of the eigenvalues of $\mathbf{A}$ (such that they correspond correctly to the columns of $\mathbf{Q}$). Using the transformation $\mathbf{y} = \mathbf{Qx}$, and recalling that orthogonal matrices preserve the standard inner product norm, the problem $\min_{\mathbf{x}^{T}\mathbf{x} = 1}\mathbf{x}^{T}\mathbf{A}\mathbf{x}$ is equivalent to $\min_{\mathbf{y}^{T}\mathbf{y} = 1} \mathbf{y}^{T}\boldsymbol{\Lambda}\mathbf{y}$. The solution to the latter problem is a vector whose only nonzero entry is a one, at the index corresponding to the minimal eigenvalue.

As Arnold Neumaier states, Lanczos would work.

share|improve this answer

$x=0$ does not satisfy the constraint, hence is irrelevant. The solution to your problem is any normalized eigenvector belonging to the smallest eigenvalue of $A$.

An eigenvector to the smallest eigenvalue of a large and sparse matrix can be found efficiently by the Lanczos algorithm, see http://en.wikipedia.org/wiki/Lanczos_algorithm

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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