Non-negative matrix factorization for audio separation - why does it work?

Non-Negative Matrix Factorization aims to factorize a matrix $\mathbf V$ into the product of two matrices, $\mathbf V = \mathbf W\mathbf H$, where $\mathbf W$ represents a set of basis vectors and $\mathbf H$ their activations or weights. Applied to audio source separation, $\mathbf V$ is the spectrogram (which is known to us), and $\mathbf W$ is the basis non-negative spectra, $\mathbf H$ is their temporal activations.

This seems to be me to be able to express a spectrogram as a sum of different frequency bins and their magnitudes - which would help to filter or separate different pitches (seemingly doing the job of a normal band-pass filter?). I do not understand how this would actually separate, say, a piano and a singer singing the same or similar pitch.

• for musical notes with harmonics, perhaps a bank of comb filters would be better than a bank of band-pass filters which would only tune in the fundamental (or perhaps another harmonic). the lowest-frequency tooth of the comb filters would be turned to the same frequency as the BPFs. so the spectrogram could be thought of as the sum of different pitched frequencies with their harmonics. there would be some overlap. Nov 29 '16 at 16:56

Recall that the columns of $\mathbf{W}$ can be thought of as "basis" vectors (or elements of a dictionary - the building blocks of any signal) and elements in each column in $\mathbf{H}$ give the corresponding weights (that vary over time). This allows us to decompose the spectrogram based on not just frequency components but also temporal onset information; so it does more than what a simple bandpass filter or comb filter would do.

Non-negative matrix factorization of a spectrogram will not magically separate a piano and a singer singing in the same pitch. However it gives a useful approximation in terms of a sum of weighted basis vectors which (hopefully) can be split up into contributions from different sources because it's unlikely for each source to occupy exactly the same frequency bin at exactly the same time instant.

More concretely, let $\mathbf{V}$ be $M\times N$, $\mathbf{W}$ be $M \times K$ and $\mathbf{H}$ be $K \times N$. So we have $M$ frequency bins, $N$ time samples and $K$ decomposed components. If $\mathbf{w}_i$ are the columns of $\mathbf{W}$ and $\mathbf{h}_i$ are the rows of $\mathbf{H}$ we can write: $$\mathbf{V} \approx \sum_{i=1}^K \mathbf{w}_i \mathbf{h}_i^T.$$ If we know there are only two sources in the recording (piano and singer) we can try to split up their contributions by choosing subsets of the columns of $\mathbf{W}$ and corresponding subset of the rows of $\mathbf{H}$. So if $S \subset \{1,\ldots,K\}$ then the part contributed by the piano can be denoted by: $$\mathbf{V}_{\mbox{piano}} = \sum_{i \in S} \mathbf{w}_i \mathbf{h}_i^T$$ and the part contributed by the singer is: $$\mathbf{V}_{\mbox{singer}} = \sum_{i \in \{1,\ldots,K\}\setminus S} \mathbf{w}_i \mathbf{h}_i^T$$

In reality, we will likely end up with a decomposition which never achieves this separation exactly. That is, there will be $\mathbf{w}_i$'s that have contributions from both the singer and the piano making it difficult to separate the two.

Here's a Python notebook showing this procedure for a mixture of drums and guitar: http://nbviewer.jupyter.org/gist/ingle/93de575aac6a4c7fe9ee5f3d5adab98f (Or if that doesn't work, here: https://gist.github.com/ingle/93de575aac6a4c7fe9ee5f3d5adab98f)

Note that the NMF algorithm only generates a decomposition. It cannot select subsets of $\{\mathbf{w}_i\}$ corresponding to each source. In the Python example, there's a manual step of figuring out which $\mathbf{w}_i$'s sound most like the guitar v/s drum. One can perhaps automate this step by noting that the drum's $\mathbf{w}_i$ vectors have more stuff in lower frequencies.

Analyzing each column (frame) of the spectrogram using a bank of bandpass filters is another way of decomposing the spectrogram. However, note that the decomposition generated by NMF is low rank i.e. parsimonious. In the Python example, it was much easier to manually select subsets of 16 columns of $\mathbf{W}$ corresponding to the two sources. With a bank of bandpass filters we would have had to turn many more knobs (# filters, locations of pass-bands for each frame) and the number of parameter combinations can grow very quickly.

References:

https://ccrma.stanford.edu/~njb/teaching/sstutorial/part2.pdf

http://musicinformationretrieval.com/nmf.html

• Pyhton notebook link is not working Nov 29 '16 at 16:46
• when the singer and piano are singing the same note (same pitch class and same octave), how is it that set $S$ and set corresponding set for the singer (which you are denoting as $\{1,\ldots,K\} \setminus S$) would be different? Nov 29 '16 at 17:02
• @robertbristow-johnson, you are right - in that case my description isn't accurate. However, I made the assumption that it is very unlikely that the singer and the piano were singing exactly the same note at exactly the same time instant/identical onsets. So there's hope that we can split it up into disjoint subsets. If not, there will $\mathbf{w}_i$'s that will have contributions from both sources. Nov 29 '16 at 17:18
• @soultrane link fixed. Nov 29 '16 at 17:33
• It's different because using a bank of bandpass filters will give a "denser" decomposition whereas NMF gives a "sparser" decomposition. The decomposition generated by NMF is low rank and parsimonious. In the Python example, it was much easier to manually select subsets of 16 columns of $\mathbf{W}$ corresponding to the two sources. With a bank of bandpass filters we would have had to turn many more knobs (# filters, locations of pass-bands for each frame) and the number of parameter combinations can grow very quickly. Nov 30 '16 at 15:45

Goal: good approximation of separating one singer from one piano. Now some thoughts about requirements for an accurate separation of the sound sources given it is unlikely to have ALL required input information to do an accurate separation ( possibly your "basis vectors"):
-- for each volume of each note of the piano the resulting frequency distribution sampled over time (as it attacks then fades). -- for each note X volume X phoneme of the singers voice the frequency distribution (and its variation with various levels of vibrato). -- for all of the above the reverb effect should be considered. -- the lyrics of the song (to match the singer's phonemes)

There are also time-domain restrictions such as each piano note must start with the attack, and the effects of the piano's sustain pedal (sudden near simultaneous dampening of notes that were "ringing" although the corresponding keys had been released)

Given the above the search is for the "best fit" sum of a set of piano note's spectrums and a singer's single note-volume-phoneme spectrum to approximate the resulting sound.