# What are the criteria for a change-of-basis transform to be doable in $O(n \log(n))$?

The Fourier basis is a common choice for transformations, but a lot of times, it's not the best for a specific application. For instance, wavelet bases give us better spatial / temporal locality than the Fourier basis, and in PCA, a specific basis is selected based on statistical analysis of a dataset.

However, if you select an arbitrary basis that's really good for your application, transforming vectors into that basis will take $$O(n^2)$$ complexity in the worst case.

My questions:

• When looking at a set of orthonormal basis vectors, is there an easy way to tell if you can transform into that basis in $$O(n \log(n))$$ time?
• If you have an arbitrary set of orthonormal basis vectors, is there a way to "round them off" / marginally rotate them to a nearby basis that will be computable in $$O(n \log(n))$$?

I'll also accept an answer that gives me terminology or academic papers that can help me further research this topic.

For context, I'm trying to do some literature review for a specific research problem related to lossy data compression and I'm not sure how to start. I have a specific idea in my head that I'm sure is already well-studied, but I don't know the vocabulary words to find this specific, obscure field of Linear Algebra / DSP.

• What is a nearby basis? Jun 24 at 17:53
• I think that we can consider a transformation between two orthonormal bases as a high-dimensional rotation. When I say that an easy-to-compute basis is 'close' to a 'target basis', I mean that you wouldn't have to rotate he 'target basis' too far to get it to the easy-to-compute approximation. Jun 24 at 20:15
• For instance, [[cos(pi/1000), sin(pi/1000)], [cos((500pi + 1)/1000), sin((500pi + 1)/1000)]] would be close to [[1,0], [0, 1]] while [[+sqrt(2)/2, sqrt(2)/2], [-sqrt(2)/2, sqrt(2)/2]] would be far. Jun 24 at 20:18
• What is «PCM»? I would guess something related to PCA but I don’t know. Jun 25 at 6:04
• hahaha oops, definitely meant to type PCA Jun 28 at 1:07

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.

• $$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...
• I wondered whether something like finding a matrix-vector multiplication technique that can be done in $N \log_2 N$ computations instead of $N^2$ might give some insight. I found this SE post and its answers but it really didn't shed any light on the question (though the history in the first answer and the discussion of big-O notation's use and abuse was interesting.
– Peter K.
Jul 9 at 0:40
• Why not even throw POSITs and UNUMs in the pond? Jul 9 at 0:46
• Agh. I meant to award this answer the full bounty, but was travelling when the timer elapsed! Thank you for this excellent and in-depth answer, this is exactly what I wanted!! Jul 15 at 22:34

The usual reason you see $$O(n \log(n))$$ computations is when the $$n^2$$ direct-approach can be decomposed into two $$n/2$$ problems, and those can be decomposed into four $$n/4$$ problems etc.

So the thing to look for is, can this "binary search" approach be used on the transform in question?

• If I manually inspect a handful of vectors, I can visually see the "binary search" thing myself, but is there a criteria you know of that can be easily automatically checked? Or, at least, what sort of keywords can I search for such a "property" of a vector basis. I guess I'm looking for a word for that "property" of vector basis. Jun 24 at 17:51

It sounds like you want to design a process that will more or less automatically arrive at the FFT for its functional and computation cost trade-off when that is optimal. And any other related (or not) transform when that is optimal, in an input data (and operation) dependent manner?

That sounds like an interesting problem. And hard. PCA/KLT/… can generate functionally optimal linear transforms for some definitions of optimal. Perhaps the simplest solution (although not so satisfying) would be to compare the PCA result to a canned list of known NlogN cost transform and pick the «closest»?

Going from the definition/idea of the FFT (or even from the DFT) to a code/hw implementation that is close to optimal for a given set of resources can be a lot of work. And that is for a well known algorithm. If a brand new algorithm was proposed by a «meta-algorithm», my hunch is that making it optimally fast may be many times as much implementation work.

• What you're describing is exactly what I want to do. My original thought was to indeed pick the "closest" from a list of known transforms, but the space is exponentially large, so it seems like manually listing a few "known" nlogn transforms would be hopelessly sparse. Jun 28 at 1:10