Abstract
This paper presents a fast algorithm for projecting a given function to the set of shift orthogonal functions (i.e., functions with unit $L^2$ norm that are orthogonal to their prescribed shifts). The algorithm can be parallelized easily, and its computational complexity is bounded by $O(M \log M)$, where $M$ is the number of coefficients used for storing the input. To derive the algorithm, a particular class of basis called Shift Orthogonal Basis Functions (SOBFs) is introduced, and the associated theory is developed.
Introduction
In computational physics and signal processing, functions that are orthogonal to their own translations—known as shift-orthogonal functions—play a vital role. A function $f(x)$ is shift-orthogonal if its inner product with its version shifted by a lattice vector $jw$ is zero for all non-zero $j$, and its $L^2$ norm is unity. Such functions are essential in constructing localized bases for electronic structure calculations and multi-resolution analysis.
However, the set of shift-orthogonal functions is not a vector space; it is a non-convex set. Consequently, finding the "closest" shift-orthogonal function to an arbitrary input—a process known as projection—is a non-trivial optimization problem. Traditional methods for this projection are often computationally expensive and scale poorly with the dimensionality of the data. This paper introduces a novel algorithm that reduces this complexity to $O(M \log M)$, offering significant performance improvements.
The Shift-Orthogonality Constraint
The primary challenge in projecting onto the set of shift-orthogonal functions lies in the global nature of the constraints. In the spatial domain, ensuring that a function does not overlap with its shifted versions involves complex integral constraints. Mathematically, for a function $f$, we require: $$\int f(x) f(x - jw) dx = \delta_{j,0}$$ where $\delta$ is the Kronecker delta. Because these constraints are coupled across the entire domain, simple optimization techniques often fail or become prohibitively slow as the resolution $M$ increases.
Methodology: The $\mathcal{B}$-Transform and SOBFs
The authors overcome these challenges by introducing Shift Orthogonal Basis Functions (SOBFs) and a specialized transform called the $\mathcal{B}$-transform.
The $\mathcal{B}$-Transform
The $\mathcal{B}$-transform acts similarly to the Fourier Transform but is specifically tailored to shift-orthogonality. Its primary utility is "decoupling": it maps the global shift-orthogonality constraints in the spatial domain to a series of independent, local constraints in a transform domain. In this new space, the requirement for shift-orthogonality simplifies into a requirement that certain vectors have unit length.
The Projection Algorithm
With the $\mathcal{B}$-transform, the projection onto the set of shift-orthogonal functions becomes a straightforward three-step process:
- Transform: The coefficients of the input function are converted into the $\mathcal{B}$-transform domain. This is achieved efficiently using an Inverse Fast Fourier Transform (IFFT).
- Normalization: In the transform domain, the projection is performed by point-wise normalization. Each decoupled component is scaled to lie on a unit sphere.
- Inverse Transform: The normalized coefficients are converted back to the original basis using a Fast Fourier Transform (FFT).
Because the transformation steps rely on the FFT, the total computational complexity is $O(M \log M)$. Furthermore, since the normalization step is independent for each point in the transform domain, the algorithm is inherently parallelizable.
Shift Orthogonal Plane Waves (SOPWs)
To implement this algorithm in periodic domains, the authors introduce Shift Orthogonal Plane Waves (SOPWs). SOPWs are a specific instance of SOBFs that can be expressed as linear combinations of standard Fourier basis functions (plane waves). This relationship allows the algorithm to leverage highly optimized FFT libraries, ensuring maximum performance on modern hardware.
Results and Performance
The algorithm was evaluated by integrating it into a framework for computing Compressed Plane Waves (CPWs), which are used to represent electronic states in quantum simulations.
In a 1D benchmark with 1,000 grid points, the proposed projection-based method demonstrated a massive speedup. A previous state-of-the-art method from 2014 required approximately 280 seconds to compute the first four CPWs. In contrast, the new algorithm completed the same task in just 6 seconds—a nearly 50-fold improvement.
Additionally, the authors provide a mathematical proof that the algorithm preserves the "real-valuedness" of functions. If the input function is real-valued, the resulting projected function is guaranteed to be real-valued, a property essential for many physical and engineering applications.
Conclusion
The introduction of SOBFs and the $O(M \log M)$ projection algorithm represents a significant advancement in the handling of shift-orthogonal constraints. By decoupling global constraints into local ones via the $\mathcal{B}$-transform, the authors have turned a difficult non-convex optimization problem into an efficient, parallelizable routine.
While the current work focuses on periodic domains and regular lattices, future research may extend these principles to non-periodic signals or irregular grids. Despite the increased complexity of calculating certain operators (like the Laplacian) in the SOBF basis, the provided explicit formulas and the sheer speed of the projection make this approach a powerful tool for high-resolution scientific computing.
Summary updated