Black-Box Toolbox: Hypercubes as Operators

Hypercubes as operators

Although it is usually easy to determine if a matrix represents a linear operator or a hypercube, there are some corner-cases where a 2-dimensional hypercube is used as a linear operator.

Mostly, the difficulties arise from a variant of the following theorem:

Schmidt-Mirsky Approximation Theorem [19]
Let X=UΣV^H be an SVD and define Σ_k to be Σ where only the largest k elements are non-zero. Then Y=UΣ_kV^H minimizes the difference X-Y, measured in any unitarily invariant norm, for any matrix Y of rank-k.

This theorem is also known as the Eckart-Young theorem, who rediscovered the result (specialized to matrices) about 30 years after Schmidt [18]. Mirsky generalized the theorem to all unitarily invariant norms.

Some variants, more or less equivalent to the theorem above possibly with some preprocessing of the data-matrix, are:

Principal Component Analysis (see also example)
Karhunen-Loève transform (after Kari Karhunen and Michel Loève)
Hotelling transform (after Harold Hotelling)
Factor analysis

The "problem" with this theorem is that it "allows" one to use the SVD on data-matrices. The easiest way to use BBTools, and remain sane, is to regard a data-matrix used as an operator as a computational trick.

References

[18] Gilbert Wright Stewart. Perturbation Theory for the Singular Value Decomposition. University of Maryland, 1990. Reference number: CS-TR-2539. (Technical report: )

[19] Gilbert Wright Stewart and Ji-guang Sun. Matrix Perturbation Theory. Academic Press, 1990. ISBN: 0-12-670230-6. (Book)