3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Oct 30, 2012 at 2:54

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

$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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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