Lecture 2: Matched filteringP. PeronaCalifornia Institute of TechnologyEE/CNS148 - Spring 20031 Detecting a signal (object) in white noisewhen the signal is knownLinear operator: prove that the matched filter k is best.The measured signal is the sum of s, the ‘clean’ object, and n, some noise.Suppose that noise is white and Gaussian.Consider a linear operator followed by threshold for detecting the object.The s ignal is processed by a linear operator k giving a response R =< k, s +n >. The response is then compared to a threshold T . If R > T the object isdeclared to be present, if R <= T the object is declared to be absent. Whichk will give minimum error rate?Response Rnto Gaussian white noise of mean µ = 0 and std σ is:Rn= < k, n >=XikiniERn=XikiEni= 0ER2n=Xi,jkikjEninj=Xik2iEn2i= σ2kkk2(1)The response to the signal is:Rs= < k, s > (2)The equal error rate value for the threshold is T = (Rs− ERn)/2 = Rs/2since the expected response when the signal is absent is zero. Clearly, the1error rate w ill be minimized when the ratio Rs/sqrt(ER2n) is minimized. Sothe best k is the solution to the problem:k∗= mink< k, s >σkkk(3)Notice that the ratio is independent of the norm of the kernel k, since itappears linearly both in the numerator and in the denominator. We may aswell set kkk = 1 from now on.The question is then how to maximize Rswith respect to k ( ERndependsonly on the norm of k which is now set to 1 and on the constant σ which wecannot change). This is quite cle arly maximized whenk =skskThis may be verified either using constrained maximization (e.g. using La-grange multipliers) or simply noting that in order to maximize the productof s and k one needs to align k with s.What do we do when the position is not known? Use the product at alllocations and consider the local maxima. This is called a correlation integral:R(x) = s ∗ k =< s(y − x), k >=Zs(y − x)k(y)dySee Matlab example.What when there are two possible signals? Use 2 filters and pick the localmaximum that is largest.2 Variable signalWhat when the signal is variable (eg. lighting, deformations, translation)?For example consider an object with Lambertian reflectance....Suppose that one could only use one kernel, then one would pick thekernel that maximizes the average product with the observed signals si:k = arg maxkXi< k, si>2= kTSSTkwhere S = [s1. . . sN]2(here, for simplicity of notation, we think of both k and the sias columnvectors).Now notice that A = SSTis a positive semidefinite symmetric matrix.Therefore its eigenvalues are real and semipositive and its eigenvectors are anorthonormal set. Call uithe set of eigenvectors of A (equivalently, they arethe left-eigenvectors of S, and call σithe corresponding e igenvalues. Supposethat they are sorted in descending order of magnitude. Then A may beexpressed in terms of the basis formed by the uiand the maximization hasa simple solution:A = SST=XiσiuiuTik = arg maxkkTAk = u1and maxkkTAk = σ1kkk2= σ1Suppose that we allowed k to belong to a r-dimensional space with r <<N. Then the solution would be ki= ui.Use principal component analysis (or, equivalently, singular value decom-position) to select suitable