Approximation error

01Compression trades information for a smaller representation#

Compression trades information for a smaller representation. After keeping $k$ SVD components, the error matrix is $A-A_k$. Its Frobenius norm measures the combined size of all omitted entries. We can compute this error directly from discarded singular values without reconstructing every entry.

SVD components are perpendicular under the matrix version of a dot product. Their squared sizes therefore add like perpendicular vector lengths. This is why discarded scales are squared, summed, and square-rooted. Adding their lengths would treat them as if they all pointed in the same direction.

A truncated SVD leaves behind the discarded singular components. Its Frobenius error combines all of their squared scales, then takes a square root.

For singular values $(10,4,3)$, keeping the largest one discards 4 and 3. Their squares total 25, giving error 5.

Link to this figure ↗Download SVGDownload PNGCopy linkCopy embed

For the complete ordered scales $(10,4,3)$ and rank 1, cross out the retained 10. The remaining scales are 4 and 3. Compute $4^2=16$, $3^2=9$, total $25$, then $\sqrt{25}=5$. The retained scale tells us which part was kept; it contributes nothing to the remaining error.

02Using only the largest discarded scale gives a different norm#

Using only the largest discarded scale gives a different norm. If discarded values are 4 and 3, Frobenius error is 5, not 4 or 7. Kept scales do not enter this error sum.

03An error budget compares against the norm, not its square#

An error budget compares against the norm, not its square. For scales $(11,4,3)$ and rank 1, the error is 5. That meets a budget of at most 5, including equality.

If a budget allows error at most 5, the error 5 passes. If the budget is 4, it fails. Keeping a second component from scales $(10,4,3)$ leaves only 3, so the error becomes 3. Raising rank cannot increase this discarded-square error, although it uses more storage.

04A closer look#

For a compressed measurement matrix, this gives a numerical way to compare storage choices. It controls aggregate reconstruction error in the specified norm. It does not promise that a visually important edge or a feature useful to a classifier survives.

Further questions