Recipe

Choose a rank for low-rank approximation

Use when: you know A's singular values (or its dimensions) and need either the storage cost at a chosen rank k, or the smallest k meeting a target relative error

Goal: a rank k (or the cost and error that rank produces), decided from the singular value spectrum alone, with no approximation ever built first

Taught in Low-rank approximation in practice

1. 1

   Square every singular value and add them: \lVert A\rVert_F^2=\sum_i\sigma_i^2. Compute this once, regardless of which rank ends up chosen.

   Example

   Singular values 10,6,3,1,0.4 give 100+36+9+1+0.16=146.16.

   Why: every relative-error calculation at every candidate rank reuses this same total, so it only needs computing once.

2. 2

   For a candidate k, add the squares of every singular value after \sigma_k, divide by the total from Step 1, and take the square root; that is the relative Frobenius error at that rank.

   Example

   At k=3: discarded squares 1+0.16=1.16, relative error \sqrt{1.16/146.16}\approx0.089. At k=2: discarded 9+1+0.16=10.16, relative error \approx0.264.

   • the resulting relative error is still above the target tolerance — try a larger k.
   • the resulting relative error already meets the tolerance — try a smaller k, to confirm this is the cheapest one that works.

   Why: checking near where the spectrum drops finds the cheapest rank meeting the budget without ever reconstructing A_k itself.

3. 3

   For an m\times n matrix at rank k, the approximation needs k(m+n+1) numbers, against mn for the original; compare the two directly.

   Example

   A 200\times150 matrix at k=10 needs 10(200+150+1)=3510 numbers versus 30{,}000 originally.

   Why: the error budget from Step 2 only matters practically once it is converted into an actual storage number to compare.

4. 4

   Before committing to a rank, look at the overall spread of the singular values; if they are all comparably sized, no small rank captures most of the total.

   Example

   Singular values 5,4.9,4.8,4.7,4.6 are nearly flat; dropping even the smallest, 4.6, removes a share of the total comparable to any other single value.

   • the largest few singular values dominate the rest — a small k captures most of \lVert A\rVert_F cheaply.
   • the singular values are all nearly equal — discarding even the smallest one removes a comparably large share of the total, so no cheap rank exists.

   Why: this step catches, before any arithmetic from Steps 1 through 3, the cases where low-rank approximation was never going to pay off.