When learning from graph data, the graph and the node features both give noisy information about the node labels. In this paper we propose an algorithm to **j**ointly **d**enoise the features and **r**ewire the graph (JDR), which improves the performance of downstream node classification graph neural nets (GNNs). JDR works by aligning the leading spectral spaces of graph and feature matrices. It approximately solves the associated non-convex optimization problem in a way that handles graphs with multiple classes and different levels of homophily or heterophily. We theoretically justify JDR in a stylized setting and show that it consistently outperforms existing rewiring methods on a wide range of synthetic and real-world node classification tasks.

Deep learning has become the state-of-the-art approach to medical tomographic imaging. A common approach is to feed the result of a simple inversion, for example the backprojection, to a multiscale convolutional neural network (CNN) which computes the final reconstruction. Despite good results on in-distribution test data, this often results in overfitting certain large-scale structures and poor generalization on out-of-distribution (OOD) samples. Moreover, the memory and computational complexity of multiscale CNNs scale unfavorably with image resolution, making them impractical for application at realistic clinical resolutions. In this paper, we introduce Glimpse, a local coordinate-based neural network for computed tomography which reconstructs a pixel value by processing only the measurements associated with the neighborhood of the pixel. Glimpse significantly outperforms successful CNNs on OOD samples, while achieving comparable or better performance on in-distribution test data and maintaining a memory footprint almost independent of image resolution; 5GB memory suffices to train on $1024\times 1024$ images which is orders of magnitude less than CNNs. Glimpse is fully differentiable and can be used plug-and-play in arbitrary deep learning architectures, enabling feats such as correcting miscalibrated projection orientations.

Relational inference aims to identify interactions between parts of a dynamical system from the observed dynamics. Current state-of-the-art methods fit the dynamics with a graph neural network (GNN) on a learnable graph. They use one-step message-passing GNNs---intuitively the right choice since non-locality of multi-step or spectral GNNs may confuse direct and indirect interactions. But the effective interaction graph depends on the sampling rate and it is rarely localized to direct neighbors, leading to poor local optima for the one-step model. In this work, we propose a graph dynamics prior (GDP) for relational inference. GDP constructively uses error amplification in non-local polynomial filters to steer the solution to the ground-truth graph. To deal with non-uniqueness, GDP simultaneously fits a ``shallow'' one-step model and a polynomial multi-step model with shared graph topology. Experiments show that GDP reconstructs graphs far more accurately than earlier methods, with remarkable robustness to under-sampling. Since appropriate sampling rates for unknown dynamical systems are not known a priori, this robustness makes GDP suitable for real applications in scientific machine learning. Reproducible code is available at https://github.com/DaDaCheng/GDP.

We propose a framework to jointly determine the deformation parameters and reconstruct the unknown volume in electron cryotomography (CryoET). CryoET aims to reconstruct three-dimensional biological samples from two-dimensional projections. A major challenge is that we can only acquire projections for a limited range of tilts, and that each projection undergoes an unknown deformation during acquisition. Not accounting for these deformations results in poor reconstruction. The existing CryoET software packages attempt to align the projections, often in a workflow which uses manual feedback. Our proposed method sidesteps this inconvenience by automatically computing a set of undeformed projections while simultaneously reconstructing the unknown volume. We achieve this by learning a continuous representation of the undeformed measurements and deformation parameters. We show that our approach enables the recovery of high-frequency details that are destroyed without accounting for deformations.

Existing statistical learning guarantees for general kernel regressors often yield loose bounds when used with finite-rank kernels. Yet, finite-rank kernels naturally appear in a number of machine learning problems, e.g. when fine-tuning a pre-trained deep neural network's last layer to adapt it to a novel task when performing transfer learning. We address this gap for finite-rank kernel ridge regression (KRR) by deriving sharp non-asymptotic upper and lower bounds for the KRR test error of any finite-rank KRR. Our bounds are tighter than previously derived bounds on finite-rank KRR and, unlike comparable results, they also remain valid for any regularization parameters.

We study representations of data from an arbitrary metric space $\mathcal{X}$ in the space of univariate Gaussian mixtures equipped with a transport metric (Delon and Desolneux 2020). We prove embedding guarantees for feature maps implemented by small neural networks called probabilistic transformers. Our guarantees are of memorization type: we prove that a probabilistic transformer of depth about $n\log(n)$ and width about $n^2$ can bi-Hölder embed any $n$-point dataset from $\mathcal{X}$ with low metric distortion, thus avoiding the curse of dimensionality. We further derive probabilistic bi-Lipschitz guarantees, which trade off the amount of distortion and the probability that a randomly chosen pair of points embeds with that distortion. If the geometry of $\mathcal{X}$ is sufficiently regular, we obtain stronger bi-Lipschitz guarantees for all points. As applications, we derive neural embedding guarantees for datasets from Riemannian manifolds, metric trees, and certain types of combinatorial graphs. When instead embedding into multivariate Gaussian mixtures, we show that probabilistic transformers compute bi-Hölder embeddings with arbitrarily small distortion. Our results show that any finite metric dataset, from vertices on a graph to functions a function space, can be faithfully represented in a single representation space, and that the representation can be implemented by a simple transformer architecture. Thus one may only need a modular set of machine learning tools compatible with this one representation space, many of which already exist, for downstream supervised and unsupervised learning from a great variety of data types.

Abstract. Unknown view tomography (UVT) reconstructs a 3D density map from its 2D projections at unknown, random orientations. A line of work starting with Kam (1980) employs the method of moments with rotation-invariant Fourier features to solve UVT in the frequency domain, assuming that the orientations are uniformly distributed. This line of work includes the recent orthogonal matrix retrieval (OMR) approaches based on matrix factorization, which, while elegant, either require side information about the density that is not available or fail to be sufficiently robust. For OMR to break free from those restrictions, we propose to jointly recover the density map and the orthogonal matrices by requiring that they be mutually consistent. We regularize the resulting nonconvex optimization problem by a denoised reference projection and a nonnegativity constraint. This is enabled by the new closed-form expressions for spatial autocorrelation features. Further, we design an easy-to-compute initial density map which effectively mitigates the nonconvexity of the reconstruction problem. Experimental results show that the proposed OMR with spatial consensus is more robust and performs significantly better than the previous state-of-the-art OMR approach in the typical low signal-to-noise-ratio scenario of 3D UVT.

We study approximation of probability measures supported on n-dimensional manifolds embedded in R^m by injective flows—neural networks composed of invertible flows and injective layers. We show that in general, injective flows between R^n and R^m universally approximate measures supported on images of extendable embeddings, which are a subset of standard embeddings: when the embedding dimension m is small, topological obstructions may preclude certain manifolds as admissible targets. When the embedding dimension is sufficiently large, m >= 3n+1, we use an argument from algebraic topology known as the clean trick to prove that the topological obstructions vanish and injective flows universally approximate any differentiable embedding. Along the way we show that the studied injective flows admit efficient projections on the range, and that their optimality can be established "in reverse," resolving a conjecture made in Brehmer & Cranmer 2020.

Injectivity plays an important role in generative models where it enables inference; in inverse problems and compressed sensing with generative priors it is a precursor to well posedness. We establish sharp characterizations of injectivity of fully-connected and convolutional ReLU layers and networks. First, through a layerwise analysis, we show that an expansivity factor of two is necessary and sufficient for injectivity by constructing appropriate weight matrices. We show that global injectivity with iid Gaussian matrices, a commonly used tractable model, requires larger expansivity between 3.4 and 10.5. We also characterize the stability of inverting an injective network via worst-case Lipschitz constants of the inverse. We then use arguments from differential topology to study injectivity of deep networks and prove that any Lipschitz map can be approximated by an injective ReLU network. Finally, using an argument based on random projections, we show that an end-to-end---rather than layerwise---doubling of the dimension suffices for injectivity. Our results establish a theoretical basis for the study of nonlinear inverse and inference problems using neural networks.

Proximal operators are of particular interest in optimization problems dealing with non-smooth objectives because in many practical cases they lead to optimization algorithms whose updates can be computed in closed form or very efficiently. A well-known example is the proximal operator of the vector L1 norm, which is given by the soft-thresholding operator. In this paper we study the proximal operator of the mixed L1,oo matrix norm and show that it can be computed in closed form by applying the well-known soft-thresholding operator to each column of the matrix. However, unlike the vector L1 norm case where the threshold is constant, in the mixed L1,oo norm case each column of the matrix might require a different threshold and all thresholds depend on the given matrix. We propose a general iterative algorithm for computing these thresholds, as well as two efficient implementations that further exploit easy to compute lower bounds for the mixed norm of the optimal solution. Experiments on large-scale synthetic and real data indicate that the proposed methods can be orders of magnitude faster than state-of-the-art methods.

Thanks to the use of convolution and pooling layers, convolutional neural networks were for a long time thought to be shift-invariant. However, recent works have shown that the output of a CNN can change significantly with small shifts in input—a problem caused by the presence of down-sampling (stride) layers. The existing solutions rely either on data augmentation or on anti-aliasing, both of which have limitations and neither of which enables perfect shift invariance. Additionally, the gains obtained from these methods do not extend to image patterns not seen during training. To address these challenges, we propose adaptive polyphase sampling (APS), a simple sub-sampling scheme that allows convolutional neural networks to achieve 100% consistency in classification performance under shifts, without any loss in accuracy. With APS, the networks exhibit perfect consistency to shifts even before training, making it the first approach that makes convolutional neural networks truly shift-invariant.

We propose injective generative models called Trumpets that generalize invertible normalizing flows. The proposed generators progressively increase dimension from a low-dimensional latent space. We demonstrate that Trumpets can be trained orders of magnitudes faster than standard flows while yielding samples of comparable or better quality. They retain many of the advantages of the standard flows such as training based on maximum likelihood and a fast, exact inverse of the generator. Since Trumpets are injective and have fast inverses, they can be effectively used for downstream Bayesian inference. To wit, we use Trumpet priors for maximum a posteriori estimation in the context of image reconstruction from compressive measurements, outperforming competitive baselines in terms of reconstruction quality and speed. We then propose an efficient method for posterior characterization and uncertainty quantification with Trumpets by taking advantage of the low-dimensional latent space

Congruent Procrustes analysis aims to find the best matching between two point sets through rotation, reflection and translation. We formulate the Procrustes problem for hyperbolic spaces, review the canonical definition of the center mass for a point set, and give a closed-form solution for the optimal isometry between noise-free point sets. Our algorithm is analogous to the Euclidean Procrustes analysis, with centering and rotation replaced by their hyperbolic counterparts. When the data is corrupted with noise, our algorithm computes a sub-optimal alignment. We thus propose a gradient-based fine-tuning method to improve the matching accuracy.

We propose a numerical interferometry method for identification of optical multiply-scattering systems when only intensity can be measured. Our method simplifies the calibration of optical transmission matrices from a quadratic to a linear inverse problem by first recovering the phase of the measurements. We show that by carefully designing the probing signals, measurement phase retrieval amounts to a distance geometry problem-a multilateration-in the complex plane. Since multilateration can be formulated as a small linear system which is the same for entire rows of the transmission matrix, the phases can be retrieved very efficiently. To speed up the subsequent estimation of transmission matrices, we design calibration signals so as to take advantage of the fast Fourier transform, achieving a numerical complexity almost linear in the number of transmission matrix entries. We run experiments on real optical hardware and use the numerically computed transmission matrix to recover an unseen image behind a scattering medium. Where the previous state-of-the-art method reports hours to compute the transmission matrix on a GPU, our method takes only a few minutes on a CPU.

In this paper, we study the problem of reconstructing a 3D point source model from a set of 2D projections at unknown view angles. Our method obviates the need to recover the projection angles by extracting a set of rotation-invariant features from the noisy projection data. From the features, we reconstruct the density map through a constrained nonconvex optimization. We show that the features have geometric interpretations in the form of radial and pairwise distances of the model. We further perform an ablation study to examine the effect of various parameters on the quality of the estimated features from the projection data. Our results showcase the potential of the proposed method in reconstructing point source models in various noise regimes.

Hyperbolic space is a natural setting for mining and visualizing data with hierarchical structure. In order to compute a hyperbolic embedding from comparison or similarity information, one has to solve a hyperbolic distance geometry problem. In this paper, we propose a unified framework to compute hyperbolic embeddings from an arbitrary mix of noisy metric and non-metric data. Our algorithms are based on semidefinite programming and the notion of a hyperbolic distance matrix, in many ways parallel to its famous Euclidean counterpart. A central ingredient we put forward is a semidefinite characterization of the hyperbolic Gramian---a matrix of Lorentzian inner products. This characterization allows us to formulate a semidefinite relaxation to efficiently compute hyperbolic embeddings in two stages: first, we complete and denoise the observed hyperbolic distance matrix; second, we propose a spectral factorization method to estimate the embedded points from the hyperbolic distance matrix. We show through numerical experiments how the flexibility to mix metric and non-metric constraints allows us to efficiently compute embeddings from arbitrary data.

We propose a general physics-based deep learning architecture for wave-based imaging problems. A key difficulty in imaging problems with a varying background wave speed is that the medium ``bends'' the waves differently depending on their position and direction. This space-bending geometry makes the equivariance to translations of convolutional networks an undesired inductive bias. We build an interpretable neural architecture inspired by Fourier integral operators (FIOs) which approximate the wave physics. FIOs model a wide range of imaging modalities, from seismology and radar to Doppler and ultrasound. We focus on learning the geometry of wave propagation captured by FIOs, which is implicit in the data, via a loss based on optimal transport. The proposed FIONet performs significantly better than the usual baselines on a number of imaging inverse problems, especially in out-of-distribution tests.

We address the problem of privately communicating audio messages to multiple listeners in a reverberant room using a set of loudspeakers. We propose two methods based on emitting noise. In the first method, the loudspeakers emit noise signals that are appropriately filtered so that after echoing along multiple paths in the room, they sum up and descramble to yield distinct meaningful audio messages only at specific focusing spots, while being incoherent everywhere else. In the second method, adapted from wireless communications, we project noise signals onto the nullspace of the MIMO channel matrix between the loudspeakers and listeners. Loudspeakers reproduce a sum of the projected noise signals and intended messages. Again because of echoes, the MIMO nullspace changes across different locations in the room. Thus, the listeners at focusing spots hear intended messages, while the acoustic channel of an eavesdropper at any other location is jammed. We show, using both numerical and real experiments, that with a small number of speakers and a few impulse response measurements, audio messages can indeed be communicated to a set of listeners while ensuring negligible intelligibility elsewhere.

We tackle the problem of recovering a complex signal x ∈ ℂnfrom quadratic measurements of the form y = x∗Aix, where $\left\{ {{{\mathbf{A}}_i}} \right\}_{i = 1}^m$ is a set of complex iid standard Gaussian matrices. This non-convex problem is related to the well understood phase retrieval problem where Aiis a rank-1 positive semidefinite matrix. Here we study a general full-rank case which models a number of key applications such as molecular geometry recovery from distance distributions and compound measurements in phaseless diffractive imaging. Most prior work either addresses the rank-1 case or focuses on real measurements. The several papers that address the full-rank complex case adopt the semidefinite relaxation approach and are thus computationally demanding. In this paper we propose a method based on the standard framework comprising a spectral initialization followed by iterative gradient descent updates. We prove that when the number of measurements exceeds the signal’s length by some constant factor, a globally optimal solution can be recovered from complex quadratic measurements with high probability. Numerical experiments on simulated data corroborate our theoretical analysis.

In this paper, we propose kinetic Euclidean distance matrices (KEDMs)-a new algebraic tool for localization of moving points from spatio-temporal distance measurements. KEDMs are inspired by the well-known Euclidean distance matrices (EDM) which model static points. When objects move, trajectory models may enable better localization from fewer samples by trading off samples in space for samples in time. We develop the theory for polynomial trajectory models used in tracking and simultaneous localization and mapping. Concretely, we derive a semidefinite relaxation for KEDMs inspired by similar algorithms for the usual EDMs, and propose a new spectral factorization algorithm adapted to trajectory reconstruction. Numerical experiments show that KEDMs and the new semidefinite relaxation accurately reconstruct trajectories from incomplete, noisy distance observations, scattered over multiple time instants. In particular, they show that temporal oversampling can considerably reduce the required number of measured distances at any given time.

In this paper, we study a 2D tomography problem for point source models with random unknown view angles. Rather than recovering the projection angles, we reconstruct the model through a set of rotation-invariant features that are estimated from the projection data. For a point source model, we show that these features reveal geometric information about the model such as the radial and pairwise distances. This establishes a connection between unknown view tomography and unassigned distance geometry problem (uDGP). We propose new methods to extract the distances and approximate the pairwise distance distribution of the underlying points. We then use the recovered distribution to estimate the locations of the points through constrained non-convex optimization. Our simulation results show that our point source reconstruction pipeline is robust to noise and outperforms the regularized expectation maximization (EM) baseline.

In this paper we tackle the problem of recovering the phase of complex linear measurements when only magnitude information is available and we control the input. We are motivated by the recent development of dedicated optics-based hardware for rapid random projections which leverages the propagation of light in random media. A signal of interest $\mathbf{\xi} \in \mathbb{R}^N$ is mixed by a random scattering medium to compute the projection $\mathbf{y} = \mathbf{A} \mathbf{\xi}$, with $\mathbf{A} \in \mathbb{C}^{M \times N}$ being a realization of a standard complex Gaussian iid random matrix. Such optics-based matrix multiplications can be much faster and energy-efficient than their CPU or GPU counterparts, yet two difficulties must be resolved: only the intensity ${|\mathbf{y}|}^2$ can be recorded by the camera, and the transmission matrix $\mathbf{A}$ is unknown. We show that even without knowing $\mathbf{A}$, we can recover the unknown phase of $\mathbf{y}$ for some equivalent transmission matrix with the same distribution as $\mathbf{A}$. Our method is based on two observations: first, conjugating or changing the phase of any row of $\mathbf{A}$ does not change its distribution; and second, since we control the input we can interfere $\mathbf{\xi}$ with arbitrary reference signals. We show how to leverage these observations to cast the measurement phase retrieval problem as a Euclidean distance geometry problem. We demonstrate appealing properties of the proposed algorithm in both numerical simulations and real hardware experiments. Not only does our algorithm accurately recover the missing phase, but it mitigates the effects of quantization and the sensitivity threshold, thus improving the measured magnitudes.

A recent unlabeled sampling result by Unnikrishnan, Haghighatshoar, and Vetterli states that with probability one over Gaussian random matrices A with iid entries, any x can be uniquely recovered from an unknown permutation of y = Ax as soon as A has at least twice as many rows as columns. We show that this condition on A implies something much stronger: that an unknown vector x can be recovered from measurements y = TAx, when the unknown T belongs to an arbitrary set of invertible, diagonalizable linear transformations T. The set T can be finite or countably infinite. When it is the set of m × m permutation matrices, we have the classical unlabeled sampling problem. We show that for almost all A with at least twice as many rows as columns, all x can be recovered either uniquely, or up to a scale depending on T, and that the condition on the size of A is necessary. Our proof is based on vector space geometry. Specializing to permutations, we obtain a simplified proof of the uniqueness result of Unnikrishnan, Haghighatshoar, and Vetterli. In this letter, we are only concerned with uniqueness; stability and algorithms are left for future work.

In this paper, we consider the problem of jointly localizing a microphone array and identifying the direction of arrival of acoustic events. Under the assumption that the sources are in the far field, this problem can be formulated as a constrained low-rank matrix factorization with an unknown column offset. Our focus is on handling missing entries, particularly when the measurement matrix does not contain a single complete column. This case has not received attention in the literature and is not handled by existing algorithms, however it is prevalent in practice. We propose an iterative algorithm that works with pairwise differences between the measurements eliminating the dependence on the unknown offset. We demonstrate state-of-the-art performance both in terms of accuracy and versatility.

We present pyroomacoustics, a software package aimed at the rapid development and testing of audio array processing algorithms. The content of the package can be divided into three main components: an intuitive Python object-oriented interface to quickly construct different simulation scenarios involving multiple sound sources and microphones in 2D and 3D rooms; a fast C implementation of the image source model for general polyhedral rooms to efficiently generate room impulse responses and simulate the propagation between sources and receivers; and finally, reference implementations of popular algorithms for beamforming, direction finding, and adaptive filtering. Together, they form a package with the potential to speed up the time to market of new algorithms by significantly reducing the implementation overhead in the performance evaluation step.

It is commonly believed that multipath hurts various audio processing algorithms. At odds with this belief, we show that multipath in fact helps sound source separation, even with very simple propagation models. Unlike most existing methods, we neither ignore the room impulse responses, nor we attempt to estimate them fully. We rather assume to know the positions of a few virtual microphones generated by echoes and we show how this gives us enough spatial diversity to get a performance boost over the anechoic case. We show improvements for two standard algorithms-one that uses only magnitudes of the transfer functions, and one that also uses the phases. Concretely, we show that multi-channel non-negative matrix factorization aided with a small number of echoes beats the vanilla variant of the same algorithm, and that with magnitude information only, echoes enable separation where it was previously impossible.

Conventional approaches to sound source localization require at least two microphones. It is known, however, that people with unilateral hearing loss can also localize sounds. Monaural localization is possible thanks to the scattering by the head, though it hinges on learning the spectra of the various sources. We take inspiration from this human ability to propose algorithms for accurate sound source localization using a single microphone embedded in an arbitrary scattering structure. The structure modifies the frequency response of the microphone in a direction-dependent way giving each direction a signature. While knowing those signatures is sufficient to localize sources of white noise, localizing speech is much more challenging: it is an ill-posed inverse problem, which we regularize by prior knowledge in the form of learned non-negative dictionaries. We demonstrate a monaural speech localization algorithm based on non-negative matrix factorization that does not depend on sophisticated, designed scatterers. In fact, we show experimental results with ad hoc scatterers made of LEGO bricks. Even with these rudimentary structures we can accurately localize arbitrary speakers; that is, we do not need to learn the dictionary for the particular speaker to be localized. Finally, we discuss multi-source localization and the related limitations of our approach.

We study simultaneous localization and mapping with a device that uses reflections to measure its distance from walls. Such a device can be realized acoustically with a synchronized collocated source and receiver; it behaves like a bat with no capacity for directional hearing or vocalizing. In this paper we generalize our previous work in 2D, and show that the 3D case is not just a simple extension, but rather a fundamentally different inverse problem. While generically the 2D problem has a unique solution, in 3D uniqueness is always absent in rooms with fewer than nine walls. In addition to the complete characterization of ambiguities which arise due to this non-uniqueness, we propose a robust solution for inexact measurements similar to analogous results for Euclidean Distance Matrices. Our theoretical results have important consequences for the design of collocated range-only SLAM systems, and we support them with an array of computer experiments.

In this paper we present FRIDA-an algorithm for estimating directions of arrival of multiple wideband sound sources. FRIDA combines multi-band information coherently and achieves state-of-the-art resolution at extremely low signal-to-noise ratios. It works for arbitrary array layouts, but unlike the various steered response power and subspace methods, it does not require a grid search. FRIDA leverages recent advances in sampling signals with a finite rate of innovation. It is based on the insight that for any array layout, the entries of the spatial covariance matrix can be linearly transformed into a uniformly sampled sum of sinusoids.

We present a new technique for estimating the specular peak of the bidirectional reflectance distribution function (BRDF) based on finite rate of innovation (FRI) sampling. The specular component of the BRDF varies rapidly, so it is challenging to acquire it by point-wise sampling. Yet, the knowledge of its precise location is key to render realistically complex materials. We show how to adapt the FRI framework to accurately determine the location of a single pulse when the sampling kernel is unknown. We use this result to determine the position of the specularity, and then estimate its shape by non-linear optimization. We demonstrate the feasibility of our approach in simulations and via a practical experiment using a custom-built BRDF acquisition device.

Recent works on reconstruction of room geometry from echoes assume that the geometry of the sensor array is known. In this paper, we show that such an assumption is not essential; echoes provide sufficient clues to reconstruct the room's and the array's geometries jointly, even from a single acoustic event. Rather than focusing on the combinatorial problem of matching the walls and the recorded echoes, we provide algorithms for solving the joint estimation problem in practical cases when this matching is known and the number of microphones is small. We then explore intriguing connections between this problem and simultaneous localization and mapping (SLAM), and show that SLAM can be solved by the same methods. Finally, we demonstrate how effective the proposed methods are by numerical simulations and experiments with real measured room impulse responses.

We address the problem of jointly localizing a robot in an unknown room and estimating the room geometry from echoes. Unlike earlier work using echoes, we assume a completely autonomous setup with (near) collocated microphone and the acoustic source. We first introduce a simple, easy to analyze estimator, and prove that the sequence of room and trajectory estimates converges to the true values. Next, we approach the problem from a Bayesian point of view, and propose a more general solution which does not require any assumptions on motion and measurement model of the robot. In addition to theoretical analysis, we validate both estimators numerically.

We propose a sampling scheme that can perfectly reconstruct a collection of spikes on the sphere from samples of their low-pass filtered observations. The proposed algorithm can reconstruct K spikes from (K + √K)2spatial samples, thus improving over previously known FRI sampling schemes on the sphere by a factor of up to four. Further, we show how multiple sound source localization (SSL) by a spherical microphone array can be transformed into a spherical FRI sampling problem. We certify the effectiveness of the proposed algorithm by using it to solve the SSL problem.

The geometry of room acoustics is such that the reverberant signal can be seen as the same waveform emitted from multiple locations. In analogy with the rake receiver from wireless communications, we propose several beamforming strategies that exploit, rather than suppress, this additional spatio-temporal diversity. Unlike earlier work in the frequency domain, time domain designs allow to shape the impulse response of the beamformer. In particular, we can control perceptually relevant parameters, such as the amount of early echoes or the length of the beamformer response. Relying on the knowledge of the image sources positions, we derive different optimal beamformers. Leveraging perceptual cues, we show how to improve interference and noise reduction without degrading the perceptual quality. The designs are validated through simulation. Using early echoes is shown to strictly improve the signal to interference and noise ratio. Code and speech samples are available online at http:// lcav.epfl.ch/Robin_Scheibler.

Depth imaging is commonly based on light. For example, LIDAR and Kinect use infrared light, while stereo cameras use visible light. These systems require hardware operating at high sampling frequencies, precise calibration, and they dissipate significant power. In this paper, we investigate the potential of ultrasound for image and depth acquisition, with applications to human-computer interaction and skeletal tracking in mind. We use a loudspeaker array and a microphone array to sense the scene. We discuss a technique for offline loudspeaker beamforming (commonly used for microphone beamforming) which enables us to significantly increase the frame rate. Further, we propose a sound-source-localization-based method for computing the depth image, giving a substantial improvement over the naive time-of-flight approach. We designed inexpensive hardware with eight elements per array to obtain both the depth and the intensity images. Even with this limited number of transducers we obtain promising experimental results.

We consider the estimation of the acoustic source position in a known room from recordings by a microphone array. We propose an algorithm that does not require the room to be convex, nor a line-of-sight path between the microphone array and the source to be present. Times of arrival of early echoes are exploited through the image source model, thereby transforming the indoor localization problem to a problem of localizing multiple sources in the free-field. The localized virtual sources are mirrored into the room using the image source method in the reverse direction. Further, we propose an optimization-based algorithm for improving the estimate of the source position. The algorithm minimizes a cost function derived from the geometry of the localization problem. We apply the designed optimization algorithm to track a moving source, and show through numerical simulations that it improves the tracking accuracy when compared with the naïve approach.

We propose a novel method for single-channel microphone localization inside a known room. Unlike other approaches, we take advantage of the room reverberation, which enables us to use only a single fixed loudspeaker to localize the microphone. Our method uses an echo labeling approach that associates the echoes to the correct walls. Echo labeling leverages the properties of the Euclidean distance matrices formed from the distances between the virtual sources and the microphone. Experiments performed in a real lecture room verify the effectiveness of the proposed localization algorithm.

Frequently, we use the Moore-Penrose pseudoinverse (MPP) even in cases when we do not require all of its defining properties. But if the running time and the storage size are critical, we can do better. By discarding some constraints needed for the MPP, we gain freedom to optimize other aspects of the new pseudoinverse. A sparser pseudoinverse reduces the amount of computation and storage. We propose a method to compute a sparse pseudoinverse and show that it offers sizable improvements in speed and storage, with a small loss in the least-squares performance. Differently from previous approaches, we do not attempt to approximate the MPP, but rather to produce an exact but sparse pseudoinverse. In the underdetermined (compressed sensing) scenario we prove that the rescaled sparse pseudoinverse yields an unbiased estimate of the unknown vector, and we demonstrate its potential in iterative sparse recovery algorithms, pointing out directions for future research.

Knowing what amount of radioactive material was released from Fukushima in March 2011 is crucial to understand the scope of the consequences. Moreover, it could be used in forward simulations to obtain accurate maps of deposition. But these data are often not publicly available, or are of questionable quality. We propose to estimate the emission waveforms by solving an inverse problem. Previous approaches rely on a detailed expert guess of how the releases appeared, and they produce a solution strongly biased by this guess. If we plant a nonexistent peak in the guess, the solution also exhibits a nonexistent peak. We propose a method based on sparse regularization that solves the Fukushima inverse problem blindly. Together with the atmospheric dispersion models and worldwide radioactivity measurements our method correctly reconstructs the times of major events during the accident, and gives plausible estimates of the released quantities of Xenon.

Acoustic source localization often relies on the free-space/far-field model. Recent work exploiting spatio-temporal sparsity promises to go beyond these scenarios. However, it requires the knowledge of the transfer functions from each possible source location to each microphone. We propose a method for indoor acoustic source localization in which the physical modeling is implicit. By approximating the wave equation with the finite element method (FEM), we naturally get a sparse recovery formulation of the source localization. We demonstrate how exploiting the bandwidth leads to improved performance and surprising results, such as localization of multiple sources with one microphone, or hearing around corners. Numerical simulation results show the feasibility of such schemes.

We study the spatio-temporal sampling of physical fields representing the dispersion of a substance in the atmosphere. We consider the following setup: N sensors are deployed at ground level and measure the concentration of a particular substance, while M smokestacks are located in the same area and emit a time-varying amount of the substance. To recover the emission rates of the smokestacks with a limited number of spatio-temporal samples, we consider time varying emissions rates lying in two specific low-dimensional subspaces. We propose efficient algorithms and sufficient conditions to recover the emission rates of the smokestacks from the local measurements collected by the sensor network.

We consider the problem of estimating room geometry from the acoustic room impulse response (RIR). Existing approaches addressing this problem exploit the knowledge of multiple RIRs. In contrast, we are interested in reconstructing the room geometry from a single RIR — a 1-D function of time. We discuss the uniqueness of the mapping between the geometry of a planar polygonal room and a single RIR. In addition to this theoretical analysis, we also propose an algorithm that performs the “blindfolded” room estimation. Furthermore, the derived results are used to construct an algorithm for localization in a known room using only a single RIR. Verification of the theoretical developments with numerical simulations is given before concluding the paper.