Abstract: We present a new computationally efficient method for multi-beamforming in the broadband setting. Our “fast
beamspace transformation” forms B beams from M sensor outputs using a number of operations per sample that
scales linearly (to within logarithmic factors) with M when B∼M . While the narrowband version of this
transformation can be performed efficiently with a spatial fast Fourier transform, the broadband setting requires
coherent processing of multiple array snapshots simultaneously. Our algorithm works by taking N samples off of
each of M sensors and encoding the sensor outputs into a set of coefficients using a special non-uniformly spaced
Fourier transform. From these coefficients, each beam is formed by solving a small system of equations that has
Toeplitz structure. The total runtime complexity is O(M log N + B log N ) operations per sample, exhibiting
essentially the same scaling as in the narrowband case. Our method offers significantly higher accuracy and lower
computational complexity than delay-and-sum filtering techniques and significantly higher accuracy and lower
latency than standard frequency- domain techniques based on sub-band processing. An additional benefit of the
proposed approach is that it allows for a careful error analysis; we give concrete formulas for the bias and variance
of the beamformer given the array parameters. We also provide a host of numerical experiments demonstrating the
algorithm’s favorable computational scaling and high accuracy. Finally, we demonstrate how tasks such as
interpolating to “off-grid” angles and nulling an interferer are more computationally efficient when performed directly
in beamspace.

Bio: Nakul Singh received a bachelor’s degree in electrical engineering from the Indian Institute of Technology, Kanpur,
India, in 2022. He is currently working toward the Ph.D. degree at the Georgia Institute of Technology, advised by
Prof. Justin Romberg and Prof. Mark Davenport. His research interests include machine learning, signal
processing, and massive MIMO.