⚡ electrical engineering

Multi-Source Position and Direction-of-Arrival Estimation Based on Euclidean Distance Matrices

This paper proposes novel multi-source position and direction-of-arrival estimation methods that leverage Euclidean distance matrices and Gram matrix eigenvalues to significantly reduce computational complexity and improve accuracy over traditional steered-response power beamforming, particularly in noisy and reverberant environments.

Original authors: Klaus Brümann, Simon Doclo

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Klaus Brümann, Simon Doclo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are in a dark, echoey room with six microphones scattered around, and two people are talking at the same time. Your goal is to figure out exactly where those two people are standing and which way they are facing, just by listening to the sound that hits the microphones.

This is a classic problem in audio engineering, but it's notoriously difficult because sound bounces off walls (reverberation) and mixes with background noise, making it hard to tell which sound came from where.

The Old Way: The "Flashlight in the Dark" Method

The traditional method, called SRP (Steered-Response Power), is like trying to find the people by shining a flashlight in every single direction and at every single spot in the room, one by one.

How it works: The computer guesses a location (e.g., "Is the person at the corner?"), calculates what the sound should sound like there, and compares it to the real recording. If it matches, it's a "hit."
The Problem: To be accurate, the computer has to check millions of spots in 3D space. It's like searching for a needle in a haystack by checking every single piece of hay individually. It takes a long time (computational cost) and can get confused if the sound bounces around too much.

The New Way: The "Geometry Puzzle" Method

The authors of this paper propose a new method based on Euclidean Distance Matrices (EDMs). Instead of guessing and checking, they treat the problem like a geometry puzzle.

Here is the simple breakdown of how their "Puzzle Method" works:

1. The "Time-Stamp" Clue

First, the system listens to the sound hitting each microphone. Since sound travels at a known speed, the tiny difference in when the sound hits one microphone versus another (called TDOA) tells us something about the distance.

Analogy: If you clap your hands and the sound hits your left ear a split second before your right ear, you know the clap is on your left.

2. The "Impossible Shape" Test

The new method takes all these time differences and tries to build a geometric shape (a triangle or a pyramid) connecting the microphones and the sound sources.

The Trick: In the real world, distances between points must follow strict geometric rules (like the sides of a triangle must add up correctly).
The Test: The computer tries different combinations of "time stamps" to see if they form a valid geometric shape.
- If the shape is "broken" or impossible (like a triangle where the sides don't connect), the computer knows that guess is wrong.
- If the shape is "perfect" (mathematically valid), it's a strong candidate for the true location.

3. Solving the Puzzle (The "Rank" Magic)

The paper uses some advanced math (Eigenvalues and Gram Matrices) to quickly check if a shape is valid.

For Position (Where are they?): Instead of searching the whole room, the computer only has to guess one number: "How far is the person from the first microphone?" It tests this one number against the "Time-Stamp" clues. If the resulting shape is geometrically perfect, it finds the location.
- Analogy: Instead of searching the whole room, you just ask, "How far away is the person?" and let the geometry tell you the rest.
For Direction (Which way are they facing?): The computer sets up a special coordinate system where one axis points directly at the speaker. It then checks if the "Time-Stamp" clues fit this specific direction. If they do, it's a match.

Why is this better?

Speed: The old method (SRP) has to check millions of spots. The new method (EDM) only has to check a few specific "time stamp" combinations and solve a simple distance equation.
- Result: In the experiments, the new method was 380 times faster for finding positions and 23 times faster for finding directions.
Accuracy in Messy Rooms: Because the new method relies on the strict rules of geometry, it is better at ignoring "fake" echoes. If an echo creates a time stamp that makes the geometry impossible, the new method instantly rejects it. The old method often gets tricked by these echoes.
Handling Multiple People: The method is smart enough to figure out which "time stamp" belongs to Person A and which belongs to Person B, even when they are talking at the same time.

The Bottom Line

Think of the old method as a brute-force search (checking every inch of the room). The new method is a logical deduction (using the rules of geometry to eliminate impossible locations instantly).

By turning a "search problem" into a "puzzle-solving problem," the authors created a system that is not only much faster but also more accurate in noisy, echoey environments. It's like switching from searching for a lost key by looking under every rug in the house to simply realizing, "The key must be in the bowl because that's the only place that fits the shape of the key."

1. Problem Statement

The paper addresses the challenge of estimating the locations (3D positions) or Directions-of-Arrival (DOAs) of multiple static sound sources in noisy and reverberant environments using microphone arrays.

Limitations of Existing Methods: The standard approach, Steered-Response Power (SRP) beamforming (specifically SRP-PHAT), requires a joint optimization over a multi-dimensional grid.
- For 3D position estimation, SRP requires optimizing three continuous variables ( $x, y, z$ ).
- For DOA estimation, it requires optimizing two continuous variables (azimuth and elevation).
Consequences: This multi-dimensional search results in high computational complexity, especially when high resolution is needed for accuracy. Furthermore, SRP performance degrades significantly when sources are close to the array (peaks become narrow) or when multiple sources interfere with each other's peaks in the functional.
Goal: To develop methods that reduce computational complexity by minimizing the number of continuous variables to be optimized while maintaining or improving accuracy in multi-source scenarios.

2. Methodology

The authors propose novel methods based on Euclidean Distance Matrices (EDMs) and their associated Gram matrices. The core premise is that the geometric consistency of source and microphone positions can be verified by analyzing the rank and eigenvalues of these matrices.

A. Theoretical Foundation

EDM & Gram Matrices: The relationship between inter-microphone distances and source-microphone distances is modeled via an EDM. The Gram matrix derived from the EDM has a rank equal to the dimensionality of the space ( $P \le 3$ ).
Cost Function: If the estimated distances (derived from Time-Differences of Arrival, TDOAs) are geometrically consistent, the Gram matrix will have exactly $P$ non-zero eigenvalues. If inconsistent, "spurious" non-zero eigenvalues appear. The cost function is defined as the sum of the absolute values of the smallest eigenvalues (those that should be zero). Minimizing this cost ensures geometric consistency.

B. Multi-Source Position Estimation (3D)

TDOA Candidates: Instead of relying on a single global TDOA peak (which may be corrupted by reverberation), the method considers $C$ candidate TDOA estimates (local maxima of the GCC-PHAT function) for each microphone pair.
Single Variable Optimization: For a specific combination of candidate TDOAs, the method assumes the sources are static and defines a single continuous variable $\alpha_s$ , representing the distance between the $s$ -th source and a reference microphone.
Exhaustive Search:
- The method performs a 1D search over $\alpha_s$ to minimize the EDM-based cost function for every possible combination of candidate TDOAs.
- It identifies the $S$ combinations (where $S$ is the number of sources) that yield the lowest cost function values, effectively solving the TDOA-to-source association problem.
Position Recovery: Once the optimal TDOA set and distance $\alpha_s$ are found, the relative source position is derived from the Gram matrix. An Orthogonal Procrustes problem is solved to map these relative positions to absolute coordinates.

C. Multi-Source DOA Estimation (Far-Field)

Rank-Reduced Gram Matrix: For far-field sources, the method defines a relative coordinate system where one axis aligns with the source DOA. By subtracting a rank-1 matrix (based on estimated TDOAs) from the microphone Gram matrix, the rank is reduced from $P$ to $P-1$ .
No Continuous Optimization: Unlike position estimation, no continuous variable optimization is required.
Selection: The method evaluates the cost function (sum of smallest eigenvalues of the rank-reduced matrix) for all candidate TDOA combinations. The $S$ combinations with the lowest costs are selected as the DOAs for the $S$ sources.
DOA Recovery: The DOA vector is extracted by solving an Orthogonal Procrustes problem to map the relative microphone geometry (derived from the rank-reduced matrix) to the absolute coordinate system.

3. Key Contributions

Dimensionality Reduction: The proposed methods drastically reduce the optimization problem. Position estimation is reduced from a 3D search to a 1D search (distance only). DOA estimation requires no continuous search at all.
Robust Association: The methods inherently solve the "association problem" (matching TDOA peaks to specific sources) by selecting the combination of TDOAs that minimizes the geometric inconsistency cost.
Handling Reverberation: By considering multiple TDOA candidates ( $C > 1$ ) rather than just the global maximum, the method is more robust to spurious peaks caused by reflections.
Computational Efficiency: Despite the combinatorial nature of TDOA combinations, the reduction in continuous variable search space leads to significantly faster runtimes compared to SRP in the tested setups.

4. Experimental Results

The authors evaluated the methods in a simulated room ( $6m \times 6m \times 2.4m$ ) with 6 microphones and 2 sources under noisy ($20$ dB SNR) and reverberant ( $T_{60} \approx 190$ ms) conditions.

Position Estimation (Spatially Distributed Mics):
- Accuracy: The EDM-based method consistently outperformed SRP. Median errors were often $< 1$ cm for EDM, whereas SRP errors ranged from $4$ cm to $>350$ cm depending on source distance.
- Robustness: SRP failed significantly when sources were close to the array (narrow peaks) or far away (peak dominance). EDM remained stable.
- Speed: The EDM method was ~380 times faster than SRP (1.6s vs 609.3s).
DOA Estimation (Compact Arrays):
- Accuracy: EDM achieved median errors $< 4^\circ$ for all configurations, significantly outperforming SRP (which showed errors up to $51^\circ$ for distant sources).
- Speed: The EDM method was ~23 times faster than SRP (1.2s vs 27.2s).
Complexity Analysis:
- While EDM complexity grows combinatorially with the number of microphones ( $M$ ) and TDOA candidates ( $C$ ), the SRP complexity grows quadratically with $M$ but exponentially with the grid resolution of the continuous variables. In the tested setup ( $M=6$ ), the EDM approach was computationally superior.

5. Significance

This paper presents a paradigm shift in multi-source localization by leveraging the algebraic properties of distance matrices rather than brute-force beamforming.

Practical Impact: The drastic reduction in computational time (orders of magnitude) makes real-time multi-source localization feasible on standard hardware, even in challenging acoustic environments.
Accuracy: The method solves the critical issue of source association and peak interference that plagues traditional SRP methods, providing superior accuracy for both near-field and far-field sources.
Flexibility: The approach is applicable to both compact arrays (DOA) and distributed arrays (3D Position) without requiring retraining (unlike learning-based methods), making it a robust model-based solution.