New algorithm cuts beamforming cost from O(M³) to O(kM²)

Adaptive beamforming is essential for large microphone arrays in environments with fast-moving talkers and interferers. However, estimating the spatial correlation matrix requires enough samples, and snapshot-deficient scenarios degrade White Noise Gain (WNG), causing target signal cancellation. A prior adaptive diagonal loading method using the Kantorovich inequality guaranteed WNG within bounds, but it needed the extreme eigenvalues of the correlation matrix—a costly O(M³) operation for large arrays.

Now, researchers from the University of Illinois Urbana-Champaign introduce a highly efficient O(kM²) estimation technique using Lanczos iterations. By projecting the M×M correlation matrix onto a small tridiagonal matrix of dimension k (k ≪ M), they extract Ritz values that rapidly converge to the exact extreme eigenvalues. Evaluations show this Lanczos-accelerated approach matches the performance of exact eigenvalue decomposition—optimal interference suppression and strict WNG adherence—at a fraction of the computational cost. This breakthrough makes real-time robust beamforming feasible for large arrays in highly dynamic acoustic environments.