SSP'05 -- Proceedings

	IEEE/SP 13th workshop on Statistical Signal Processing July, 17-20, 2005 - Bordeaux - France

Information regarding the paper

Title

A Signal Processing Application Of Randomized Low-Rank Approximations

Author(s)

Peter Parker	MIT Lincoln Laboratory
Patrick Wolfe	Harvard University
Vahid Tarokh	Harvard University

Get the paper in PDF format

To obtain Acrobat Reader (version 5 minimum required) necessary to his read.

Abstract

Low-rank approximations to linear operators find wide use in signal processing. In the discrete case, assuming the desired rank is known a priori, such approximations are generally calculated using the singular value decomposition. In this vein, randomized algorithms have recently been developed in the context of theoretical computer science, with the goal of achieving approximations arbitrarily close to this optimal low-rank solution with very high probability. Such algorithms function by finding (deterministic) low-rank approximations to random submatrices chosen probabilistically - thereby providing significant reductions in computational complexity, and leading to their applicability even in the case of very large matrices. Here it is demonstrated that algorithms of this type also show promise in signal processing applications, in particular for the case of adaptive beamforming in both the narrowband and wideband scenarios. Quantitative simulation results are provided to indicate that near-optimal nulling performance, as measured in terms of signal-to-interference-plusnoise ratio, may be achieved via straightforward modifications of the randomized algorithms described above. Results indicate that a large computational savings is possible, relative to standard methods, with little corresponding loss in performance.