Skip to content
nonconvexcard

Implement power iteration and verify the convergence rate

CodingIntermediate⏱ 1 hourFoundationspower iterationeigenvalueconvergence rateimplementation

Problem

Implement power iteration for a symmetric matrix AA: starting from a random unit vector v0v_0, repeat vt+1=Avt/∥Avt∥2v_{t+1} = Av_t/\|Av_t\|_2 and estimate λmax⁡\lambda_{\max} by the Rayleigh quotient vt⊤Avtv_t^\top A v_t.

  1. Test it on a diagonal matrix with known spectrum.
  2. Measure the error ∣λt−λ1∣|\lambda_t - \lambda_1| against tt on a log scale and verify that it decays geometrically with ratio (λ2/λ1)2(\lambda_2/\lambda_1)^2.
  3. Construct a matrix with λ1=λ2\lambda_1 = \lambda_2 and explain what happens.

Implement it, then check the implementation against something you can verify independently.

Write it

Solve it here5 tests · Python runs in your browser
⌘/Ctrl + ↵ to run · limit 30s · draft saved in this browser
5 tests will run against your code. The first run downloads the Python runtime — several megabytes, once per browser.

Hints

Hints — 0 of 3 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Equality in Cauchy–SchwarzFoundationsProofBeginner15 min
Bounding the spectral norm by row and column sumsFoundationsProofIntermediate30 min
Characterising orthogonal projectorsFoundationsProofIntermediate30 min
Implement backpropagation from scratch runDeep LearningCodingIntermediate3 hours
Implement kernel ridge regression runClassical MLCodingIntermediate1 hour