Von Mises Iteration

gistfile1.scala

object VonMises extends App {
  type Matrix = Seq[Seq[Double]]
  type Vector = Seq[Double]

  def dot(a:Vector, b:Vector) = a.zip(b).map(i=>i._1 * i._2).sum // dot product aka inner product
  def mult(m:Matrix, v:Vector) = m.map{ row => dot(row,v) } // matrix vector multiplication
  def l2(v:Vector) = math.sqrt(v.map{i=> i*i}.sum) // l2 norm of vector
  def scale(v:Vector, c:Double) = v.map{i=> i*c }

  // computes the dominant eigen value and associated eigen vector via Von Mises Iteration aka Power Method
  def vonMisesStep(guess:Vector, m:Matrix): (Double, Vector) = {
    val result = mult(m,guess)
    val eigen = l2(result)
    (eigen, scale(result, 1.0/eigen)) // aka normalize matrix
  }

  // Goal : To compute dominant eigenvalue of symmetric matrix below
  val symmetric = Seq(Seq(7.0,1,2,4), Seq(1,8.0,3,2), Seq(2,3,9.0,1), Seq(4,2,1,11.0))
  val TOL = math.pow(10.0,-4) // error tolerance bound

  // Guess the eigenvalue via Gershgorin ie. max(7 + (1+2+4), 8 + (1+3+2), 9+ (2+3+1), 11+ (4+2+1)) = 18
  // Pick a random eigenVector say (1,1,1,1)
  val (guessEigen, guessVector) = (18.0, Seq(1,1,1,1.0))

  // Von Mises Iteration, given matrix A & vector x = Simply perform A*x/||A*x||, until convergence!
  val result = (0 to 1000).foldLeft ((guessEigen, guessVector, true)) { (a,b) =>
    val (guessEigen, guessVector, mustCompute) = a
    if (mustCompute) {
      val (eigen, eigenVector) = vonMisesStep(guessVector, symmetric)
      println(eigen + "," + eigenVector)
      (eigen, eigenVector, math.abs(eigen - guessEigen) > TOL)
    } else a
  }

  val dominantEigen = result._1
  println(dominantEigen)
}

gistfile2.txt

$ scala VonMises
30.675723300355934,List(0.4563869566471659, 0.4563869566471659, 0.4889860249791063, 0.5867832299749276)
15.517396223184162,List(0.44957288727423744, 0.4348672320830241, 0.4684801582343689, 0.6239399416843389)
15.560849919731929,List(0.45078498683506496, 0.4229737537449112, 0.4526750706373084, 0.642628492762776)
15.575697549145609,List(0.4529063787774337, 0.41589515935272947, 0.44217572546413536, 0.6529836569929948)
15.58120866954994,List(0.4545556150298058, 0.4115574266397968, 0.4355286913681571, 0.6590253685691043)
15.583283578778744,List(0.4556552893981052, 0.40887735933059394, 0.43139605763295524, 0.6626424403319738)
15.584066422016377,List(0.4563524095138551, 0.4072202367310342, 0.42884504177773186, 0.6648353835877527)
15.584361852047207,List(0.45678602619839437, 0.4061969463984988, 0.4272748767017002, 0.6661732107687621)
15.58447334139543,List(0.4570537335609393, 0.40556600858884534, 0.4263095612624318, 0.6669919454472832)
15.584515414543533,List(0.4572185184006327, 0.40517746038230046, 0.4257163802158496, 0.6674938319157666)
15.584515414543533