The Taub Faculty of Computer Science Events and Talks

While the solution of linear inverse problems (BIPs) under both classical signal models and modern sparsity models has been studied extensively and is well understood, relatively little is known about the solution of bilinear inverse problems. In signal processing, these problems arise in so-called blind signal recovery applications. One notable example is blind deconvolution, with applications in blind image deblurring, blind channel equalization, speech dereverberation, and seismic data analysis. Another important example, is blind gain and phase calibration, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution.

Without further constraints, these bilinear inverse problems do not admit a unique solution. Nonetheless, in practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, existing theoretical analysis on uniqueness in these problems is rather limited. We describe a framework for identifiability in bilinear inverse problems, and derive the first algebraic results on sample complexity that guarantee recovery under minimal requirements. We also propose a practical recovery algorithm for blind deconvolution that achieves guaranteed optimal scaling of the sample complexity up to logarithmic factors, both in theory and in numerical experiments.