# Matched Subspace Detectors

2146 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 42, NO. 8, AUGUST 1994 Matched Subspace Detectors Louis L. Scharf, Fellow, IEEE, and Benjamin Friedlander, Fellow, IEEE Abstract-In this paper we formulate a general class of prob- lems for detecting subspace signals in subspace interference and broadband noise. We derive the generalized likelihood ratio (GLR) for each problem in the class. We then establish the invariances for the GLR and argue that these are the natural invariances for the problem. In each case, the GLR is a maximal invariant statistic, and the distribution of the maximal invariant statistic is monotone. This means that the GLR test (GLRT) is the uniformly most powerful invariant detector. We illustrate the utility of this finding by solving a number of problems for de- tecting subspace signals in subspace interference and broadband noise. In each case we give the distribution for the detector and compute performance curves. I. INTRODUCTION HE matched filter, or more accurately the matched signal T detector, is one of the basic building blocks of signal processing; however, in many applications the rank- 1 matched signal detector is replaced by a multirank matched subspace detector. In fact, the matched subspace detector is really the general building block, and the matched signal detector is a special case. In sonar signal processing, the matched subspace detector is called a matched field detector. In [l], one of the authors developed a theory of matched subspace detectors based on the construction of invariant statistics. In this paper we extend this work in two ways. First, we include structured interference in the measurement model, and second we use the principle of the generalized likelihood ratio test (GLRT) to derive matched subspace detectors. By studying the invariance classes for these GLRT’s, we are able to establish that the GLRT’s are invariant to a natural set of invariances and optimum within the class of detectors which share these invariances. This establishes once and for all the optimality of the GLRT for solving matched subspace detection problems and answers “no” to the question, “can the GLRT be improved upon?” This result holds for all finite sample sizes, thereby improving on the standard asymptotic theory of the GLRT. Our program in this paper is to derive GLRT’s for the class of problems studied in [l], [4]-161 and generalize them Manuscript received July 3, 1993; revised November 11, 1993. This work was supported by the Office of Naval Research, Mathematics Division, Statistics and Probability Branch, under Contracts N00014-89-Jl070 and N00014-91-J1602, and by the National Science Foundation under Grant MIP- 90-17221. The associate editor coordinating the review of this paper and approving it for publication was Prof. Kevin M. Buckley. L. L. Scharf is with the Department of Electrical that is, y = p z + w (2.1) where p = 0 under HO and p 0 under HI. This is the standard detection problem wherein the polarity of the signal z is assumed known. Near the end of Section V we replace H1 : p 0 with H1 : p # 0 in order to model problems where polarity is unknown. We shall assume that the signal z obeys the linear subspace model z = ~ e , H E I R ~ ~ P , e E w (2.2) and the noise is MVN with mean Scp and covariance R = w:Af[Scp,a2 (b) resolving a measurement into signal plus interference plus noise. We shall assume that H, S, and y) = (27rU2)-N/2exP{ - Ilnll;} (2.7) which is a function of (/3, 02) with the data y playing the role of a parameter. For any two values (Pl, U!) and (Po, U,“), the likelihood ratio is defined to be We expect Z(y) to be greater than one whenever the parameters () better model y than do the parameters ( EHSS = 0 ESHS = S; ESHH = 0. (3.3) That is, any vector y E (HS) may be written as y = HB + S4 = PHSY = (EHS + E s H ) ~ . The second decomposition resolves P H ~ into the orthog- onal projections P s and Ppl H . The subspace (PhH) is S the subspace spanned by columns of the matrix PiH; the projector P i projects onto the subspace (S)l. Geometrically, the subspace ( P i H ) is the part of (H) which is unaccounted for by the subspace (S) , when (H) is resolved into (S) @ (S) I. The ranges of PPl H and P s are (PhH) and (S), and the S IV. THE GLRT AND ITS NATURAL INVARIANCES The question we pose is this: “What can we say about the (generalized) likelihood ratio when unknown parameters are replaced by maximum likelihood estimates (MLE’s) of them?” In other words, what kinds of invariances does the estimated likelihood ratio have, and how is it distributed? As we shall see, these questions underlie a systematic discussion of the GLRT, its invariances, and its optimality. When the parameters (ai,a!) are replaced by their MLE’s(Bi, 8?), then the corresponding MLE of the likelihood ratio is called the generalized likelihood ratio (GLR): SCHARF AND FRIEDLANDER: MATCHED SUBSPACE DETECTORS 2149 Note that a, = @i,i), whereas So = (O,’$), with 4 differing under H1 and Ho. Thus, in this formula, ii1 and EL0 are the v. KNOWN SIGNAL IN SUBSPACE INTERFERENCE AND NOISE OF KNOWN LEVEL The problem here is to test HO : y = S4 + n versus H1 : y = ,uz+S4+n where p 0. The signal z is known, the subspace interference S4 lies in the rank-t subspace (S), and the noise n is drawn from the normal distribution N[O, a21] MLE’s n1=y-fiH8-S$ (4-2) jL0 = y - s+. with a’ known. We may write the detection problem as a test . of distributions: We shall have more to say about these MLE’s shortly. When a’ is known, then there is no need to estimate a’, and it will be convenient to replace the GLR by the logarithmic GLR HO : y : N[Sd, 2 1 1 versus : y : N[pz + ~ 4 , a24. 1 (5.1) Ll(y) = lni(y) = ;;Z [IliLOll; - ~ ~ i i l ~ ~ ~ ~ ~ (4.3) When 2 is unknown, then 6: = T E 7. (4.7) By studying the invariance class 7, we gain geometrical in- sight into the mathematical structure of the GLR. Furthermore, we will be able to show that, of all detectors that are invariant- 7, the GLRT is the uniformly most powerful (UMP). This is the strongest statement of optimality that we could hope to make about a test of HO versus HI, meaning that the GLRT cannot be improved upon by any detector which shares its invariances. We will argue that the invariances are so natural that no detector would be accepted which did not have them. With these preliminaries established, we now undertake a study of four closely related problems, ranging from the detection of known-form signals in subspace interference and Gaussian noise to the detection of subspace signals in subspace interference and Gaussian noise of unknown level. fi1 = max(0, ji) b 5 0 . (5.5) { (STP$S)-lSTPjy, j i 0 n 1 = { $1 = The corresponding MLE’s for the noises nl and no are PhY, b 5 0 PiSY, f i o iio = Piy. (5.6) GLR: With these results for the estimated noises, we may write the logarithmic GLR as 2150 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 42, NO. 8, AUGUST 1994 less than or equal to zero. The random variable ( T - ~ P P ~ ~ ~ is distributed as follows: 1 CL - PPl ,y : N [ - Pp1 zz, Ppgz] . (5.10) OS f J S Therefore, ( T - ~ ~ ~ P I y is chi-squared distributed with one degree of freedom (the rank of PPlz) and noncentrality parameter X2 [I]: PSZ S / : orthogonal subspace Fig. 3. interference and noise of known level. Invariances of the GLRT for detecting known signal in subspace Invariances: The GLR Ll(y) is invariant to transforma- tions T E 71, where 71 is the set of rotations and translations of y in the space (P = (zTP+- zTP(zTP p 0, a unknown. (6.1) For this problem, the MLE s ir0 and ii1 remain unchanged from Section V, but now the estimated variances are 6 : = Iliill12/N and 8; = )lir011~/N. (These results for 8; and 1 5 . 2 2 are obtained by differentiating log-likelihood or by positing them and then using a variational argument.) GLR: The N/2-root GLR is It is actually more natural to reference X2 is the signal energy after it has passed through the null-steering operator f i L 0 o. LdY) - 1 = y (Ph-P;s,y, (6.3) { O Y P k S Y Pi. The receiver operating characteristics (ROC S) for this de- tector are given in Fig. 4, and the detector diagram is given in Fig. 5. Note the interference rejecting filter P i followed by a matched filter. Note: When the test Ho versus HI is replaced by the two- sided test H1 : p # 0 versus H1 : p = 0, then the constraint that fi1 0 is not enforced. The logarithmic GLR is then We now Call h ( Y ) - 1 Simply h ( Y ) and use the identities Of (3.6) and (3.7) to write this GLR as 1 h ( Y ) = 7YTPp1 Y. (5.18) SZ This statistic is invariant to T E 71, and it has monotone likelihood ratio. Therefore, the test where PG is the projector PG = PPi ,, The GLR may also S is UMP-invariant. The distribution of Ll(y) is chi-squared with one degree of freedom and nonconcentrality parameter X2: Ll(Y) XW) where E,, is the oblique projection 2152 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 42, NO. 8, AUGUST 1994 , : “ s T a l subspace“ With these results we see that the GLR Lz(y) has a mixed distribution, which we write as z = LZ(Y) : y(p)S(z) + (1 - Y(p))Fl,N--t--1(A2) (6.10) that is, z = Lz(y) has discrete probability mass of y(p) at z = 0 and continuous probability (1 -y(p))F1,N--t-1(A2) on the positive real axis. The distribution of that is, Lz(y) = (N - t - 1) 1/2D2 (6.13) Furthermore, D ; G :PiH Fig. 12. Invariances for Lz. Section VII, and it should be invariant to scalings that intro- duce unknown variances. These are the natural invariances for the problem. Oprimality and Pedormance: The (N/2)-root GLR is the unique invariant statistic for testing HO versus HI. It is the ratio of quadratic forms in P ~ P G P ~ and PhPbPh. Each of the quadratic forms may be thought of as a norm- squared of a statistic P G P ~ Y or PbP$y. These statistics are, respectively, distributed as PbPhy : N[0,a2Pb], Ho or HI. (8.4) Furthermore, the random vectors P$PGY and PhPey are uncorrelated (and therefore independent in this multivariate normal case) by virtue of the fact that P ~ P G P $ P ~ = PGPb = 0: E P G P ~ ( Y - H6)yTP$Pb = P G P $ P ~ P ~ = 0. (8.5) This means that the quadratic forms $ y T P h P ~ P h y and $ y’P$PbP$y are independent x2 random variables: The parameter s is the dimension of (S)’-, namely s = N-t p, the number of dimensions of RN not occupied by (S), and p is the dimension of (G) = (PhH). The noncentrality parameter X2 is The GLR ((s - p)/p) L2 is distributed as (8.7) ‘0 z 4 fi 8 io 12 14 ifi 18 m SNR IdEl Fig. 13. and broadband noise of unknown level; p = 2 and N is variable. ROC curves for detecting subspace signal in subspace interference where F denotes an F-distribution with parameters p and s-p. This distribution is monotone in X2 2 0, so the GLRT is UMP-invariant for testing HO versus HI. Its false alarm and detection probabilities are PFA = 1 - P[Fp,s-p(O) I 711 P D = 1 - P[Fp,s-p(X2) 5 771. (8.10) The ROC curves for the GLRT are given in Figs. 13 and 14, and the detector diagram is given in Fig. 15. In Fig. 13, the probability of false alarm is fixed at PFA = 0.01, the dimension of the subspace (H) is p = 2, and N is varied from N = 8 to N = 64 in powers of 2. The ROC for the x2 distributed matched subspace detector is plotted for reference. In Fig. 14, the probability of false alarm is fixed at PFA = 0.01, the number of measurements is fixed at N = 16, and the subspace dimension is varied from p = 2 to p = 8 in steps of 2. The normal ROC is plotted for reference. The detector of Fig. 15 decomposes into a subspace filter for interference rejection, a subspace filter matched to the remaining signal, and an energy computation, divided by the same operations with the matched subspace filter replaced by an orthogonal (or “noise”) subspace filter. These results generalize the results of [l], [5]-[6]. In summary, the GLRT is UMP invariant for detecting sub- space signals in subspace interferences and background noise whenever the noise is MVN. The conclusion holds whether or not the noise variance is known. When the interference is absent, then PIH = H and the GLRs are y T P ~ y and YTPHY/YTPHy, which are distributed as $(A2) and Fp,~-p(X2) as discussed in [l]. The parameter X2 is then s A2 = $TZ. IX. CONCLUSIONS 3 - P Fp,s-p(X2) under HI (8.8) The generalized likelihood ratio test (GLRT) is a standard - P Lz(y) ’ { Fp,s-p(0) under HO procedure for solving detection problems when (nuisance) 2156 I EEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 42, NO. 8, AUGUST 1994 . . ::: 0 2 4 6 8 10 12 14 16 18 U) SNR IdBl Fig. 14. and broadband noise of unknown level; p is variable and N = 8. ROC curves for detecting subspace signal in subspace interference Fig. 1 5 . Detector diagram. parameters of the underlying distribution are unknown. Typi- cally, nuisance parameters are things like bias, amplitude and phase of sinusoidal interference, noise variance, and so on. These parameters are of no intrinsic interest, but they defeat our efforts to state properties of optimality if we proceed along conventional lines. The GLRT is easy to derive, and sometimes its distribution can be determined. In these cases, a detection threshold may be set to achieve a constant false alarm rate (CFAR). In spite of its tractability as a bootstrapping technique for solving detection problems, the GLRT has been difficult to characterize in terms of its optimality properties for the class of problems studied in this paper. In fact, it has not been clear whether or not the GLRT has any optimality properties at all for this class. So the question has remained, “can the GLRT be improved upon?“ In this paper we have constructed GLRT s for four detection problems which span a large subset of the practical detection problems encountered in time series analysis and multisensor array processing. For each class of problems we have derived the GLRT and established its invariances. Then we have drawn on the theory of invariance in hypothesis testing to establish that, within the class of invariant detectors which have the same invariances as the GLRT, the GLRT is uniformly most powerful (UMP) invariant. This is the strongest statement of optimality one could hope to make for a detector. For each class of problems, the invariances of the GLRT are just the invariances one would expect of a detector that claims to be optimum. The conclusion is that the GLRT cannot be improved upon for the classes of problems studied in this paper. The geometrical interpretation of our results is this: Think of the plane I in Fig. 2 (i) as a backplane onto which measurements y are projected to produce the interview-tree vector Ps I y. This projection can be resolved into its two orthogonal components, PGPS I y and P, Ps I y. These two components are tested to see which of two competing hypotheses is in force. For detecting a deterministic rank one signal in interference and additive noise, when the noise level os known, the component PGP, I y is tested to see i