Channel Mixing and Pseudo-Inverses

Let’s say we want to mix three channels onto two because the communication device has only two available channels but we still want to emulate a three channel link. If we can afford coding, then it’s not a problem because we can build our own protocol so add any number of channels using a structured data stream. But what if we cannot control the channel coding at all? In CDs, for example, there’s no coding: there are two channels encoded in PCM and a standard CD player wouldn’t understand the sound if it was encoded otherwise.

The solution is to mix the three channels in a quasi-reversible way, and in a way that the two channels can be listened to without much interference. One possible way is to mix the third channel is to use a phase-dependant encoding. Early “quadraphonic” audio systems did something quite similar. You can also use a plain time-domain “mixing matrix” to mix the three channels onto two. Quite expygeously, let us choose the matrix:

M=\left[~\begin{array}{ccc} \frac{2}{3} &0&\frac{1}{3}\\ 0 &\frac{2}{3}&\frac{1}{3}\end{array}~\right]

and we compute the mixing of the three original channels x, y, z onto the mixed channels u and v as:

\left[~\begin{array}{ccc}\frac{2}{3} & 0 & \frac{1}{3} \\ 0 & \frac{2}{3} & \frac{1}{3} \\ \end{array}~\right]\left[\begin{array}{c}x \\ y \\ z \end{array}\right]=\left[\begin{array}{c}u \\ v \end{array}\right]

Which is a standard matrix-vector multiplication, so no big deal. At the other end, you want to decode [u,v] into the best approximation of [x,y,z] you can, but lo! the mixing matrix isn’t square, it’s singular, so you cannot use the straight matrix inverse to recover [x,y,z]. So let A be our matrix. In general, if A is non-invertible, we can use the normal equations to solve for the best-effort inverse of A. Consider that x and y are vectors (unrelated to our channels):

Ax=y

A^TAx=A^Ty

x=(A^TA)^{-1}A^Ty

and the (A^TA)^{-1}A^T part is the Moore-Penrose Pseudo-Inverse of the matrix A, denoted A^+. However, this method works if (A^TA)^{-1} exists. Unfortunately for us, M^TM is still singular, thus non-invertible.

Ach! Großes malheur! Well, no, not that much. If MM^T is non-singular, therefore invertible, we can use a variant of the pseudo-inverse that’s the “right” pseudo-inverse of M, so that instead of M^+M=I, we’ll have MM^+\approx{}I. Indeed, let the right pseudo-inverse be:

M^+=\left(\left(MM^T\right)^{-1}M\right)^T

We can show rather quickly that it is indeed an inverse of M:

M\left(\left(MM^T\right)^{-1}M\right)^T\overset{?}{=}I

M\left(M^T\left((MM^T)^{-1}\right)^T\right)\overset{?}{=}I

M\left(M^T\left((M^{-T}M^{-1})\right)^T\right)\overset{?}{=}I

M M^T M^{-T} M^{-1}\overset{?}{=}I

M I M^{-1}\overset{?}{=}I

M M^{-1}\overset{?}{=}I

I=I

And we’re done. ■

So, using the right pseudo-inverse, we find that:

M^+=\left[~\begin{array}{cc}\frac{5}{4} & -\frac{1}{4}\\ -\frac{1}{4} & \frac{5}{4}\\ \frac{1}{2} & \frac{1}{2} \end{array}~\right]

and we can recover a good approximation of the original [x,y,z] vector:

\left[\begin{array}{c} u \\ v \end{array} \right]^T\left[~\begin{array}{cc}\frac{5}{4} & -\frac{1}{4}\\ -\frac{1}{4} & \frac{5}{4}\\ \frac{1}{2} & \frac{1}{2} \end{array}~\right]^T\approx\left[\begin{array}{c} x \\ y \\ z \end{array}\right]

*
* *

Let us see what such a channel mixing might look like. I have written a small C++ program that reads a picture and produces a [u,v] image (mapped onto the red-green plane for display purposes) and recovers the best-effort inverse in [\tilde{r},\tilde{g},\tilde{b}], where the tilde denotes approximation. So, using the above equations, replacing [x,y,z] by [r,b,g], getting [u,v], then, using the pseudo-inverse, [\tilde{r},\tilde{g},\tilde{b}].

Let me demonstrate with this otter picture (sorry, don’t know the source):

otter

Using the mixing matrix M we get a [u,v] image:

otter-uv

Which is of course rendered using the red-green plane for display purposes. The [u,v] plane isn’t really a color plane; it’s a projection of the RGB space onto an arbitrary plane. Using the pseudo-inverse M^+, we recover a good approximation of the original image:

otter-reconstructed

Which of course, isn’t quite the original because, despite M^+ being the best-effort inverse of M, the original transform is a surjective mapping of a 3D space onto a 2D plane.

*
* *

So why is the pseudo-inverses so interesting? In general, they’re useful as soon as you have to inverse a singular matrix to solve a problem. Square matrices can be singular by having a determinant of zero, resulting from insufficient rank, for example. It can also be that the matrix is rectangular. Rectangular matrices can have exact inverses in some rare cases, but in general, we must rely on a best-effort inverse. Rectangular matrices are seen in the context of least squares regression.

In the case of simple linear regression, we have direct formulae to find the slope and intercept of a line passing through a cloud of points that minimizes the square error. If we want to fit a more complex function, the algebraic method of computing partial derivative and isolating the sought variable one by one becomes increasingly painful with each added variable. Using the matrix notation of the problem—and the pseudo-inverse—provides a “one size fits all” solution to all regression problems where the function is a linear combination of functions of input values.

*
* *

You can choose between the left and right pseudo-inverse in order to minimize computation time. Indeed, if A is m\times{}n, A^TA is m\times{}m while AA^T is n\times{}n. As the matrix inverse is a rather expensive computation, in the order of O(n^3) for a n\times{}n matrix, it may be quite a bit faster to invert the smallest of the two pseudo-inverse kernels!

*
* *

Ah, also, before you ask, I’m sure you were wondering about some of the operations used in the demonstrations. The only thing one must really know is that matrix multiplication is associative but not commutative. That is, A(BC)=(AB)C but AB \neq BA in general. Also, you need the following rules:

(AB)^{-1}=B^{-1}A^{-1}

(AB)^T=B^TA^T

(A^{-1})^T=(A^T)^{-1}

(A+B)^T=A^T+B^T

One Response to Channel Mixing and Pseudo-Inverses

  1. […] a number of previous occasions, I have used the pseudoinverse of a matrix solve systems of equations, and do other […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: