gtsam 4.1.1 gtsam
gtsam::AcceleratedPowerMethod< Operator > Class Template Reference

## Detailed Description

template<class Operator>
class gtsam::AcceleratedPowerMethod< Operator >

Compute maximum Eigenpair with accelerated power method.

References : 1) G. Golub and C. V. Loan, Matrix Computations, 3rd ed. Baltimore, Johns Hopkins University Press, 1996, pp.405-411 2) Rosen, D. and Carlone, L., 2017, September. Computational enhancements for certifiably correct SLAM. In Proceedings of the International Conference on Intelligent Robots and Systems. 3) Yulun Tian and Kasra Khosoussi and David M. Rosen and Jonathan P. How, 2020, Aug, Distributed Certifiably Correct Pose-Graph Optimization, Arxiv 4) C. de Sa, B. He, I. Mitliagkas, C. Ré, and P. Xu, “Accelerated stochastic power iteration,” in Proc. Mach. Learn. Res., no. 84, 2018, pp. 58–67

It performs the following iteration: $$x_{k+1} = A * x_k - \beta * x_{k-1}$$ where A is the aim matrix we want to get eigenpair of, x is the Ritz vector

Template argument Operator just needs multiplication operator

Inheritance diagram for gtsam::AcceleratedPowerMethod< Operator >:

## Public Member Functions

AcceleratedPowerMethod (const Operator &A, const boost::optional< Vector > initial=boost::none, double initialBeta=0.0)
Constructor from aim matrix A (given as Matrix or Sparse), optional intial vector as ritzVector.

Vector acceleratedPowerIteration (const Vector &x1, const Vector &x0, const double beta) const
Run accelerated power iteration to get ritzVector with beta and previous two ritzVector x0 and x00, and return y = (A * x0 - \beta * x00) / || A * x0. More...

Vector acceleratedPowerIteration () const
Run accelerated power iteration to get ritzVector with beta and previous two ritzVector x0 and x00, and return y = (A * x0 - \beta * x00) / || A * x0. More...

double estimateBeta (const size_t T=10) const
Tuning the momentum beta using the Best Heavy Ball algorithm in Ref(3), T is the iteration time to find beta with largest Rayleigh quotient.

bool compute (size_t maxIterations, double tol)
Start the accelerated iteration, after performing the accelerated iteration, calculate the ritz error, repeat this operation until the ritz error converge. More...

Public Member Functions inherited from gtsam::PowerMethod< Operator >
PowerMethod (const Operator &A, const boost::optional< Vector > initial=boost::none)
Construct from the aim matrix and intial ritz vector.

Vector powerIteration (const Vector &x) const
Run power iteration to get ritzVector with previous ritzVector x, and return A * x / || A * x ||.

Vector powerIteration () const
Run power iteration to get ritzVector with previous ritzVector x, and return A * x / || A * x ||.

bool converged (double tol) const
After Perform power iteration on a single Ritz value, check if the Ritz residual for the current Ritz pair is less than the required convergence tol, return true if yes, else false.

size_t nrIterations () const
Return the number of iterations.

bool compute (size_t maxIterations, double tol)
Start the power/accelerated iteration, after performing the power/accelerated iteration, calculate the ritz error, repeat this operation until the ritz error converge. More...

double eigenvalue () const
Return the eigenvalue.

Vector eigenvector () const
Return the eigenvector.

Protected Attributes inherited from gtsam::PowerMethod< Operator >
const Operator & A_
Const reference to an externally-held matrix whose minimum-eigenvalue we want to compute.

const int dim_

size_t nrIterations_

double ritzValue_

Vector ritzVector_

## ◆ acceleratedPowerIteration() [1/2]

template<class Operator >
 Vector gtsam::AcceleratedPowerMethod< Operator >::acceleratedPowerIteration ( ) const
inline

Run accelerated power iteration to get ritzVector with beta and previous two ritzVector x0 and x00, and return y = (A * x0 - \beta * x00) / || A * x0.

• \beta * x00 ||

## ◆ acceleratedPowerIteration() [2/2]

template<class Operator >
 Vector gtsam::AcceleratedPowerMethod< Operator >::acceleratedPowerIteration ( const Vector & x1, const Vector & x0, const double beta ) const
inline

Run accelerated power iteration to get ritzVector with beta and previous two ritzVector x0 and x00, and return y = (A * x0 - \beta * x00) / || A * x0.

• \beta * x00 ||

## ◆ compute()

template<class Operator >
 bool gtsam::AcceleratedPowerMethod< Operator >::compute ( size_t maxIterations, double tol )
inline

Start the accelerated iteration, after performing the accelerated iteration, calculate the ritz error, repeat this operation until the ritz error converge.

If converged return true, else false.

The documentation for this class was generated from the following file: