Chapter 7A Best NonorthogonalBasisIn this section, we examine a particular question whos e solution will involvegetting an optimal nonorthogonal basis, which is quite contrary to our earlierchapters- in fact, the reader should ask why we would ever want to use a non-orthogonal basis when it would be q uite easy (using Gram-Schmidt) to constructan or tho gonal version of the same basis.To answer this question, consider the synthetic data example in Figure 7.1.Here there is a definite “natural” basis appearing in the data- and the basisvectors are not orthogonal. While the data was synthetic, we do get similartypes of data appearing in the problem of Blind Signal Separation. Considerthe following tasks:1. We have a patient that is pregnant. Our overall goal is to listen to thefetus heartbeat, but when we try, the sound of the mother’s heartbeat ismixed with the heartbeat of the fetus. Symmetrically, if we were to try tolisten to the heartbeat of the mother, we would als o hear the heartbeatof the fetus. Is it possible to gather these sounds on micropho nes andmanipulate the data so that the mother’s (or fetus) heartbeat has beenisolated?2. We have two microphones placed at random, but distinct, places in aroom. We a lso have two people speaking in the room (the placement ofthe people is distinct from the placement of the microphones- we do notassume that each microphone is placed in front of each speaker). Is itpossible to manipulate the two mixtures of voices so that we can isolateeach speaker’s voice?The answer lies in a fairly new technique called Independent ComponentAnalysis (ICA) (versus wha t we studied earlier, principal components analysis,or PCA). In ICA, we assume that we have some underlying, statistically inde-115116 CHAPTER 7. A BEST NONORTHOGONAL BASIS−0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8−0.6−0.4−0.200.20.40.6Figure 7.1: A synthetic data example of a naturally emerging set of basis vectorsfrom data- These are not orthogonal.pendent, process e s and that we are observing mixtures of these pro cesses. Ourgoal is to separate the mixtures.This problem is also known as Blind Signal Separation, where we assumesome unknown mixture of signals, and we attempt at separating them.This process (the problem and the so lution) can also be framed in otherterms- we will focus on the geometric meaning of the problem, and will solve itusing the techniques of linear algebra.7.1 Set up the Signal Separation ProblemWe will assume that there exists a “clean” separation of our observed mixtureof two signals (we will be explicit in what we mean by that momentarily, and wewill discuss the more general case in a moment). These signals, as time se ries,are two columns of a matrix S, so that S ∈ IRp×2, where p is the length of thesample.We will further assume that the mixtures we are observ ing are linear mix-tures, so that the mixtures we observe may be modeled as:x1= α1s1+ α2s2x2= α3s1+ α4s2so that x1is the observed mixture in microphone 1, and x2is the observedmixture in microphone 2. In linear algebra terms, we can state the problem asfollows:Given x1, x2as columns of X ∈ IRp×2, solve the following equation for7.1. SET UP THE SIGNAL SEPARATION PROBLEM 117−30 −20 −10 0 10 20 30 40−100−80−60−40−20020406080100Figure 7.2: The synthetic data s et after the SVD transformation as describedin the text. In this case, the principal co mponents analysis has left the desiredbasis vectors in a rotated position. We require one more rotation (multiplicationby an orthogonal matrix) to get the desirable results.A ∈ IR2×2and S ∈ IRp×2:X = SAWe assume that the rows of X have been mean-subtracted.If you look at this equatio n, something should be occurring to you- this isnot a well defined problem! There are an infinite number of s olutions for A, S.In fact, one solution would be to let A be the 2 × 2 identity matrix, and S = X.We could also give a solution in terms of the SVD of X, which is what wewould do in Pr incipal Component Analysis:X = UxΣxVTxso that S = Ux, and A = ΣxVTx. In this c ase the da ta is “separated” in thesense that the columns of Uxare orthogonal (or uncorrelated). Figure 7.2 showsthe result of this op e ration on our synthetic data. It also shows that the desiredbasis vectors are still rotated.This process, while not the desired o ne, is a good first step, but somehowwe need the signals to be independent, and not just uncorrelated.Alternatively, let us consider the SVD of the unknown mixing matrix A,A = UmΣmVTm. The problem will be solved if we knew this matrix, as S couldbe computed by using the inverse of A (we assume that A is full rank- see theexercises for a discussion). Let’s try some sample computations now by taking118 CHAPTER 7. A BEST NONORTHOGONAL BASISour o riginal equation and substituting the SVD of A:X = SA ⇒ X = SUmΣmVTmNow c ompute the 2 × 2 covariance of X:XTX = VmΣmUTmSTSUmΣmVTmNow, if the rows of S are statistically independent, then they certainly shouldbe uncorrelated. We will assume therefor e that SSTis some scalar multiple ofthe identity:SST= cI2×2which also assumes that the variances of the signals are the same. In particular,we’ll ass ume that the signals in S have been scaled so that STS = I. In theexercises, we will examine this assumption in mo re detail.Using this, we s e e that:XTX = VmΣ2mVTm= VxΣxVTxThis tells us that Vmand Σmare recoverable from the SVD of X: IfX = UxΣxVTxthenΣm= Σ1/2x, Vm= VxIf we were to stop here and take:Y = XVxΣ−1/2x= SUmΣmVTmVxΣ−1/2x= SUmwe obtain the standard PCA solution. However, the signals are still rotated.We ca nnot perform another covariance computation on Y , since now:YTY = UTmSTSUm= I2×2How can we compute Um? There is some justification for what we’re about todo- Let’s do it first and then discuss it.Define dA to be the difference matrix for the matrix A. That is, if A hasbeen orga nized so that it comprises p samples of k time series of data, then letA be p × k. We compute the difference as:dA = A(2 : p, :) − A(1 : p − 1, :)so that dA is now p − 1 × k and(dA)ij= Ai+1,j− Ai,jIf the data in A were the sample of some differentiable function, then dA is anapproximation to the derivative using ∆t = 1.7.1. SET UP THE SIGNAL SEPARATION PROBLEM 119Note that the following matrix equation holds:X = SA ⇒ dX = dS Aso thatdXTdX = ATdSTdS AMore particular ly, letY = XVxΣ−1/2x, or dY = dXVxΣ−1/2x= dS Umso that dYTdY =