For the first question, nothing comes to my mind: I have no knowledge about a known criterion. I tend to suppose that the problem is very combinatoric to find some sparse decomposition, hence difficult.
For the second question, I have better news. There have been algebraic approach by Markus Püschel, as you can see from Using Algebra to Discover Transform Algorithms
Two recent papers addressed that problem, resorting to Givens rotation $G_j$ decomposition:
We study the problem of approximating orthogonal matrices so that
their application is numerically fast and yet accurate. We find an
approximation by solving an optimization problem over a set of
structured matrices, that we call extended orthogonal Givens
transformations, including Givens rotations as a special case. We
propose an efficient greedy algorithm to solve such a problem and show
that it strikes a balance between approximation accuracy and speed of
computation. The approach is relevant to spectral methods and we
illustrate its application to PCA.
We analyze effective approximation of unitary matrices. In our
formulation, a unitary matrix is represented as a product of rotations
in two-dimensional subspaces, so-called Givens rotations. Instead of
the quadratic dimension dependence when applying a dense matrix,
applying such an approximation scales with the number factors, each of
which can be implemented efficiently. Consequently, in settings where
an approximation is once computed and then applied many times, such a
representation becomes advantageous. Although effective Givens
factorization is not possible for generic unitary operators, we show
that minimizing a sparsity-inducing objective with a coordinate
descent algorithm on the unitary group yields good factorizations for
structured matrices. Canonical applications of such a setup are
orthogonal basis transforms. We demonstrate numerical results of
approximating the graph Fourier transform, which is the matrix
obtained when diagonalizing a graph Laplacian.
The latter indeed aims at estimating best $\|U-\prod_j G_j\|$ approximations, but is cautious at the end:
We showed that effective Givens factorization of generic orthogonal
matrices is impossible and inspected a distribution of planted
factors, which allows us to control approximability. Our initial
results suggest that sparsity inducing factorization is promising
beyond the sparse matrix regime. However, it remains an open problem
to further characterize the matrices that admit effective
factorization using manifold coordinate descent on an L1-criterion.
Additional bits:
- $O(\cdot)$-type analyses are asymptotic. For a given orthogonal matrix size, ad hoc optimization can be more efficient in terms of basic operations. With more processors/cache, only checking the number of multiplies and adds can be misleading on actual performance. Being able to work with integers or dyadic rationals, taking care of data proximity (for faster addressing) can be useful as well. I remember works of Markus Püschel et al., like SPIRAL: Code Generation for DSP Transforms
- Connected is the work of Gilbert Strang, on Groups of banded matrices with banded inverses, 2011, Proceedings of the American Mathematical Society
- Let me recall the useful book: Fast Transforms Algorithms, Analyses, Applications, by Douglas Elliott, K. Rao, and a copy seems to be available. It also talks about efficient Walsh-Hadamard, breeds of DCTs, slant transforms...
