Transformée de Hadamard | EPFL Graph Search

La transformée de Hadamard (aussi connue sous le nom de « transformée de Walsh-Hadamard ») est un exemple d'une classe généralisée d'une transformée de Fourier. Elle est nommée d'après le mathématicien français Jacques Hadamard et effectue une opération linéaire et involutive avec une matrice orthogonale et symétrique sur 2 nombres réels (ou complexes, bien que les matrices utilisées possèdent des coefficients réels). Ces matrices sont des matrices de Hadamard. La transformée de Hadamard peut être vue comme étant issue d'une transformée de Fourier discrète et s'avère être en fait l'équivalent d'une transformée de Fourier discrète multidimensionnelle d'une taille de 2×2×...×2×2.
Elle décompose un vecteur arbitraire en entrée en une superposition de fonctions de Walsh. Définition formelle La transformée de Hadamard H{{ind|m}} utilise une matrice 2×2 (une matrice de Hadamard) multipliée par un facteur de normalisation, et transforme 2 nombres réels x{{

Rake, Peel, Sketch

Robin Scheibler

The prototypical signal processing pipeline can be divided into four blocks. Representation of the signal in a basis suitable for processing. Enhancement of the meaningful part of the signal and noise reduction. Estimation of important statistical properties of the signal. Adaptive processing to track and adapt to changes in the signal statistics. This thesis revisits each of these blocks and proposes new algorithms, borrowing ideas from information theory, theoretical computer science, or communications. First, we revisit the Walsh-Hadamard transform (WHT) for the case of a signal sparse in the transformed domain, namely that has only K â€ N non-zero coefficients. We show that an efficient algorithm exists that can compute these coefficients in O(K log2(K) log2(N/K)) and using only O(K log2(N/K)) samples. This algorithm relies on a fast hashing procedure that computes small linear combinations of transformed domain coefficients. A bipartite graph is formed with linear combinations on one side, and non-zero coefficients on the other. A peeling decoder is then used to recover the non-zero coefficients one by one. A detailed analysis of the algorithm based on error correcting codes over the binary erasure channel is given. The second chapter is about beamforming. Inspired by the rake receiver from wireless communications, we recognize that echoes in a room are an important source of extra signal diversity. We extend several classic beamforming algorithms to take advantage of echoes and also propose new optimal formulations. We explore formulations both in time and frequency domains. We show theoretically and in numerical simulations that the signal-to-interference-and-noise ratio increases proportionally to the number of echoes used. Finally, beyond objective measures, we show that echoes also directly improve speech intelligibility as measured by the perceptual evaluation of speech quality (PESQ) metric. Next, we attack the problem of direction of arrival of acoustic sources, to which we apply a robust finite rate of innovation reconstruction framework. FRIDA â the resulting algorithm â exploits wideband information coherently, works at very low signal-to-noise ratio, and can resolve very close sources. The algorithm can use either raw microphone signals or their cross- correlations. While the former lets us work with correlated sources, the latter creates a quadratic number of measurements that allows to locate many sources with few microphones. Thorough experiments on simulated and recorded data shows that FRIDA compares favorably with the state-of-the-art. We continue by revisiting the classic recursive least squares (RLS) adaptive filter with ideas borrowed from recent results on sketching least squares problems. The exact update of RLS is replaced by a few steps of conjugate gradient descent. We propose then two different precondi- tioners, obtained by sketching the data, to accelerate the convergence of the gradient descent. Experiments on artificial as well as natural signals show that the proposed algorithm has a performance very close to that of RLS at a lower computational burden. The fifth and final chapter is dedicated to the software and hardware tools developed for this thesis. We describe the pyroomacoustics Python package that contains routines for the evaluation of audio processing algorithms and reference implementations of popular algorithms. We then give an overview of the microphone arrays developed.

EPFL2017

A Fast Hadamard Transform for Signals with Sub-linear Sparsity

Saeid Haghighatshoar, Robin Scheibler, Martin Vetterli

A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT, where N is a power of two and K = O(N^α), scales sub- linearly in N for some 0 < α < 1. Assuming a random support model for the nonzero transform domain components, the algorithm reconstructs the WHT of the signal with a sample complexity O(K log2(N/K)), a computational complexity O(K log2(K) log2(N/K)) and with a very high probability asymptotically tending to 1. The approach is based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time domain signal, one can induce a suitable aliasing pattern in the transform domain. By treating the aliasing patterns as parity-check constraints and borrowing ideas from erasure correcting sparse-graph codes, the recovery of the nonzero spectral values has been formulated as a belief propagation (BP) algorithm (peeling decoding) over a sparse-graph code for the binary erasure channel (BEC). Tools from coding theory are used to analyze the asymptotic performance of the algorithm in the “very sparse” (α ∈ (0, 1/3]) and the “less sparse” regime (α ∈ (1/3,1).)

2013

A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain

Saeid Haghighatshoar, Robin Scheibler, Martin Vetterli

In this paper, we design a new iterative low-complexity algorithm for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT. We suppose that N is a power of two and K = O(N^α), scales sub-linearly in N for some α ∈ (0,1). Assuming a random support model for the nonzero transform-domain components, our algorithm reconstructs the WHT of the signal with a sample complexity O(K log_2(N/K)) and a computational complexity O(K log_2(K) log_2(N/K)). Moreover, the algorithm succeeds with a high probability approaching 1 for large dimension N. Our approach is mainly based on the subsampling (aliasing) property of the WHT, where by a carefully designed subsampling of the time-domain signal, a suitable aliasing pattern is induced in the transform domain. We treat the resulting aliasing patterns as parity-check constraints and represent them by a bipartite graph. We analyze the properties of the resulting bipartite graphs and borrow ideas from codes defined over sparse bipartite graphs to formulate the recovery of the nonzero spectral values as a peeling decoding algorithm for a specific sparse-graph code transmitted over a binary erasure channel (BEC). This enables us to use tools from coding theory (belief-propagation analysis) to characterize the asymptotic performance of our algorithm in the very sparse (α ∈ (0,1/3]) and the less sparse (α ∈ (1/3,1)) regime. Comprehensive simulation results are provided to assess the empirical performance of the proposed algorithm.

Institute of Electrical and Electronics Engineers2015

Rake, Peel, Sketch

Robin Scheibler

EPFL2017