Point, Plane, Set, Match! Winning the Echo Grand SLAM

Some of the most important and challenging problems in science are inverse problems. They allow us to understand phenomena that cannot be measured directly. Inverse problems might not always have a unique or stable solution, or might not have any solution at all; in these cases, they are called ill-posed. An example of an inverse problem in room acoustics is simultaneous localization and mapping (SLAM) from sound. It is the central theme of this thesis, and we address it both from a theoretical and practical viewpoint. From a theoretical perspective, we show that our SLAM setup is ill-posed since the uniqueness condition is not satisfied. From a practical perspective, we propose methods to constrain and identify a solution set, and we use real experiments to confirm that such a constrained problem is stable. The acoustic SLAM problem consists of jointly reconstructing the geometry of a room and self-localizing. We show that it can be reformulated as the reconstruction of a set of points and planes from their pairwise distances; to solve the problem, we introduce point-to-plane distance matrices (PPDMs). Our motivation for PPDMs comes from the need of a robust localization system in indoor environments. Inspired by echolocation in animals, we approach the problem with the following analogy: Imagine that a bat loses the directivity in its sensing and becomes what we call an omnidirectional bat. It explores the room by moving randomly and listening to the echoes of its chirps. Can it still map the room and localize itself without any prior knowledge of the room geometry and its own trajectory? Our research shows that the answer is yes, but not in all rooms. We emulate such a bat using a device equipped with a collocated speaker and microphone. At different locations, the speaker emits a pulse and the microphone registers the room impulse response. The propagation times of the first-order echoes directly reveal the distances between the device and the walls. The problem is then to recover the locations of the device and walls from their pairwise distances; in the PPDM framework, its solution corresponds to the factorization of a PPDM. Though the most popular, SLAM is not the only application of PPDMs. In fact, our abstraction can be adapted to solve other problems in computer vision and signal processing which appear quite different at first glance, but they all rely on the factorization of a low-rank matrix. One famous example of such a problem is structure from motion (SFM), and aims at recovering a scene geometry and camera motions from images. A similar example in acoustics is called structure from sound (SFS), and concerns the joint localization of sensors and acoustic events. In both SFM and SFS, the idea is to factor a low-rank measurement matrix into the product of a projection and coordinate matrix. Finally, we can envision problems in which the projection matrix from SLAM, SFM or SFS is known, and the goal is to recover the coordinate matrix only. To solve these problems, we introduce another low-rank matrix named coordinate difference matrix (CDM). Possible applications include phase retrieval, where the core problem can be stated as the recovery of points from their unlabeled and noisy pairwise differences, and optimal tournament design, where we rely on CDMs to devise an active learning algorithm from pairwise comparisons. In a nutshell, this thesis revolves around the theory, algorithms and applications of PPDMs and CDMs.