L2 Minimal Algorithms

Abstract

We consider putting certain tensors into forms with approximately minimum L2 norm. These tensors describe strategies for computing linear or bilinear maps. Such forms are of interest from a practical perspective because they are particularly numerically stable. They are of interest from a theoretical perspective because they may be unique up to certain orthogonal or unitary transformations. The main tensors of interest represent (commutative, real) "matrix multiplication algorithms" or "bilinear algorithms." We explain how an algorithm's L2 minimal form might be thought of as optimally stable and as close to attaining the nuclear norm as possible. We demonstrate an algorithm "Strop" that has minimum L2 norm among all rank 7 algorithms for 2x2 matrix multiplication. This leads to better error for typical large matrices than Strassen, at the cost of more operations. Putting Strassen's (or any such) algorithm into this form requires "only" a convex optimization problem on positive definite matrices. In some situations, this optimization enables us to check when algorithms are equivalent in a natural sense. As a stepping stone we consider L2 minimal forms for analogous "linear algorithms." Such forms have been the subject of extensive study by invariant theorists, but are less known in other circles. We give simple examples of when the existence of these forms, and their use in equivalence testing, is apparent from an optimization perspective.