Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell University Graduate School
  3. Cornell Theses and Dissertations
  4. L2 Minimal Algorithms

L2 Minimal Algorithms

File(s)
Turner_cornellgrad_0058F_12746.pdf (329.35 KB)
Permanent Link(s)
https://doi.org/10.7298/gbet-ps76
https://hdl.handle.net/1813/110662
Collections
Cornell Theses and Dissertations
Author
Turner, Abigail
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.

Description
43 pages
Date Issued
2021-08
Committee Chair
Strogatz, Steven H.
Committee Member
Elser, Veit
Damle, Anil
Degree Discipline
Mathematics
Degree Name
Ph. D., Mathematics
Degree Level
Doctor of Philosophy
Type
dissertation or thesis
Link(s) to Catalog Record
https://newcatalog.library.cornell.edu/catalog/15160049

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance