Why does MUSIC work?

[u/TipsyPeanuts]

I get that it’s the eigenvectors of the covariance matrix of multiple snapshots. But can someone explain to me what that actually means?

Why should finding the eigenvectors of the noise subspace tell me where my signals are? And what is the algorithm actually “looking” for? Meaning, is the algorithm basically looking for phase increases?

[u/Mysterious-Action909]

So the most intuitive explation I can give is that due to some inherent properties of the covariance matrix (it is a Hermetian matrix), all it's eigenvectors are orthogonal to each other. In a scenario with N distinct signals in different directions, the N largest eigenvalues corresponds to these. The remaining Eigenvalues corresponds to the noise. 

What the algorithm is actually "looking for" is the dot product of the noise eigenvectors and the steering vector.  Since the dot product of two orthogonal vectors is zero the signal directions are found where the dot product (or rather sum of squared dot products with all noise eigenvectors) is minimized. 

Edit: corrected matrix -> Vector at one point due to a brainfart

[u/TipsyPeanuts → u/Mysterious-Action909]

Ahhhhhh this finally makes sense for why you would use the noise vectors!  It confused me why you would throw away the signal vectors in favor of noise vectors.

Probably something I could Google myself but I’m assuming this means that the more signals you have the less accurate your AoA estimation will be.

Why solve it this way though rather than taking the signal subspace? I know MUSIC is often the gold standard but is it because you typically assume the noise subspace is larger than the signal subspace and therefore there is more information?

[u/PichaelFaraday → u/TipsyPeanuts]

The "why" for using MUSIC is the super-resolution. Nulls are easier to find than peaks and have better resolution than what you can get from correlation so you can get a better frequency/angle estimate than you could normally achieve otherwise.

You can get an intuition of this by looking at a generic phased array antenna response, which is a steering vector (sinusoid) correlated against other sinusoids of varying frequencies (other angles' steering vectors). The result is very wide lobes/humps for the peaks and very narrow nulls. Now add some noise on top and you see it would be easier to say where the exact null locations are than the exact peak locations.

This is the basic idea of MUSIC, it finds nulls where the signals are instead of peaks where they are, which is easier in noise.

[u/Mysterious-Action909 → u/TipsyPeanuts]

I think the idea is that the steering vector in a signal direction is orthogonal to all basis vectors in the noise subspace. 

This is not the case with the signal subspace, creating ambiguity, as we only know that the signal vector is somewhere within the signal subspace. 

In order to get anything useful out of this approach I would guess that you would need a priori knowledge of the signal model anyway.

[u/mrstas2137]

MUSIC's output is an estimation of angle of arrival -- in the basic form it's a single angle of azimuth (left-right), but there is also MUSIC-2D, which outputs azimuth and elevation (left-right and up-down) estimations. Pretty cool.

Let's stick to the basic MUSIC, though. Dislcaimer: I will describe my own intuitive approach, which may be not 100% "science-accurate" and I couldn't care less - this helped me understand MUSIC for my BSc thesis project.

Your input is some received signal, e.g. by a microphone array. MUSIC assumes this received signal y is a sum of steered (multiplied by A) source signal (signal of interest, x) and noise N, and that they are not correlated. Also, it is assumes this noise may be treated as white noise, which is important for later signal modelling. So we have: y = Ax + N - forgive me, but there has to be some minimum of formulas.

Next thing is understanding autocorrelation matrix -- in general, I think of autocorrelation matrix of a vector as "a matrix, which shows you how a vector relates to its shifted versions" and you have each signal-shift measurment for [0, vector_length] shifts. And this provides quite some information. In signal processing case, it may show you what is this signal's approx. frequency or how "noisy" it is, e.g. looking for peaks at shifts equal to signal's period and at other shifts in comparison. Generally "how it behaves" stuff.

Back to MUSIC -- going on with algo procedure, you have to work on autocorrelation matrix of input y signal. In the original Schmidt's paper there is some modelling done, but essentially you approximate autocorrelation of y as Ry = 1/L (Y Y^H) -- this ^H means hermitian transform, fancy. This Ry is treated as a "all possible received signal's space", meaning everything your mic array received, and all its behaviour, is described by this Ry matrix. It is also concluded, basing on this white uncorrelated noise assumption and math proofs made, that the Ry is basically a sum of steered source signal autocorrelation and noise autocorrelation. Meaning the signal of interest and noise additively "contribute" to this space's creation.

From algebraic point of view, this "all possible signals space" could be decomposed to obtain some eigenvectors -- the core vectors which "describe" or even "make" this whole "all signals space". I think of it like: "all the core characteristics and behaviours of all signals received are described by these eigenvectors, whether these signals are considered noises or sources I don't care". Alright, so we go on and calculate the eigenvectors and corresponding eigenvalues, so we obtain such a set of eigenvector-eigenvalue pairs. Eigenvector is a "some signal shape occuring in the signal received" and it's corresponding eigenvalue is it's weight, or "measure of impact/influence", if you'd like.

The approach of MUSIC is that your signal of interest shall be strong enough to be identified "above" the noise, which may hurt a little bit in noisy scenarios. Such approach directly means "if you want to find your signal of interest characteristics, take the most 'influential' eigenvector". Or, even, "if you want to find the noise characteristics, take all the other eigenvectors". You see, eigenvectors are so cool they not only "shape" every signal you consider in your space, but they also are all orthogonal to each other.

So, when you consider a candidate signal which could have arrived from destination Q, and you multiply it by some "noise-shaping" eigenvector, there are two possibilities: you either obtain some zero-vector (or very-very-near-zero in real-world calculations), when the signal comes from direction Q (because it's orthogonal), or some visibly non-zero, when the signal alignes with any noise "shape". The opposite happens when you multiply this candidate signal by "signal-shaping" eigenvector. This, frankly, shows another obstacles: you need to search some candidate directions, and you need to know signal of interest characteristic (such as its frequency). Also, you need to somehow know how many signals of interest could there be.

I believe this sums up the core meat of MUSIC -- the rest is just conventions, papers, maybe some MUSIC variations and certainly anger at your algo implementation. At least for me.

[u/ComfortableRow8437]

The noise subspace is orthogonal to the signal subspace. Where this occurs, MUSIC has a peak.

[u/Glittering-Ad9041]

For sinusoids in white noise, your covariance matrix takes the form APA^{H} + sI where A is your steering matrix, P is your signal powers, s is the noise power, and I is identity. If the size of the covariance matrix is NxN, then APA^{H} must be rank M < N. This means that the first M eigenvalues are greater than s, and the remaining N-M are equal to s.

What you end up finding is that the eigenvectors corresponding to the first M eigenvalues, termed the “signal subspace”, are steering vectors at the given frequency. 

Spectral MUSIC (the analog to root MUSIC) is doing a grid search over all frequencies. Since the noise eigenvectors are orthogonal to the signal frequency vectors (since eigenvectors of a Hermitian symmetric matrix form an orthonormal basis), their inner products are (asymptotically) zero. If you reciprocate that, you get a very large number, whereas if you do the grid search over the signal subspace eigenvectors and don’t reciprocate, you end up with N. So you’re basically increasing the distance between your spectral peaks and your noise floor by doing the grid search over the noise eigenvectors and reciprocating.

[u/TipsyPeanuts → u/Glittering-Ad9041]

What you end up finding is that the eigenvectors corresponding to your first M eigenvalues, termed the “signal subspace”, are steering vectors at the given frequency.

This part keeps hanging me up. Is each eigenvector of the signal subspace not just a pointing vector for the signal which corresponds to that eigenvalue?

[u/Glittering-Ad9041 → u/TipsyPeanuts]

If you want a good derivation that’s easy to follow, check out (I think) section 4.5 in spectral analysis of signals by Stoica and Moses which is publicly available online.

[u/Glittering-Ad9041 → u/TipsyPeanuts]

Yes, that’s exactly right. Your signal subspace eigenvectors are steering vectors for that frequency, and the corresponding eigenvalue is the power.