Let F denote the female training set and M the male training set. Let d = |F |+|M|, andlet N2be the number of pixels in each image. Determining the optimal decision boundaryrequires finding w ∈ RN2satisfying Sw = mF−mM, where mF, mM∈ RN2are the meansof F and M, respectively, and S ∈ RN2×N2is the within-class scatter matrix given byS =Xx∈F(x − mF)(x − mF)T+Xx∈M(x − mM)(x − mM)T.(For brevity we use the notation S instead of SW.) In our case, N = 256, so representingS in a computer is cumbersome (indeed, disallowed by MATLAB’s standard settings). Weseek a means to solve Sw = mF− mMwithout computing S explicitly.We may represent S by S = CCT, where C ∈ RN2×dis the matrix whose ithcolumn isthe ithelement of F ∪M. C has the singular value decomposition C = UΣVT, where• U ∈ RN2×N2is a unitary matrix whose ithcolumn is the ith(normalized) eigenvectorof S;• Σ ∈ RN2×dsatisfies σi,i=√λifor 1 ≤ i ≤ d, where λiis the ith(necessarily non-negative) eigenvalue of CTC ∈ Rd×d, and σi,j= 0 when i 6= j;• V ∈ Rd×dis a unitary matrix whose ithcolumn is the ith(normalized) eigenvector ofCTC ∈ Rd×d.Henceforth let B = CTC.Therefore,S = (UΣVT)(UΣVT)T= UΣVTV(UΣ)T= UΣ(UΣ)T,and thus we seek w satisfyingUΣ(UΣ)Tw = mF− mMUTUΣ(UΣ)Tw = UT(mF− mM)Σ(UΣ)Tw = UT(mF− mM)ΣTΣ(UΣ)Tw = ΣTUT(mF− mM)(ΣTΣ)(UΣ)Tw = (UΣ)T(mF− mM).For i from 1 to d, the (i, i)thentry of ΣTΣ ∈ Rd×dis σ2i= λi; all other entries are 0. In thisspirit, let Λ = ΣTΣ. Under the reasonable assumption that no eigenvalue of B is 0, Λ isinvertible, and(UΣ)Tw = Λ−1(UΣ)T(mF− mM).Let A = UΣ ∈ RN2×d. For i from 1 to d, let eibe the itheigenvalue of B. ThenCTCei= λieiCCTCei= λiCeiS(Cei) = λi(Cei).1Thus Ceiis the itheigenvector of S, and is hence the ithcolumn of U. (For i > d, theithcolumn of U is a basis vector of the kernel of S.) Therefore, the ithcolumn of A isσiCei=√λiCei.Without loss of generality we may assume that w ⊥ ker S, because we are trying to solveSw = mF− mM. Therefore, there exists a ∈ Rdsuch that w =Pdi=1aiCei. Therefore,ATdXi=1aiCei= Λ−1AT(mF− mM)ATCdXi=1aiei= Λ−1AT(mF− mM)dXi=1aiei= (ATC)−1Λ−1AT(mF− mM);this operation is valid becauseATC = (UΣ)T(UΣVT) = ΣTUTUΣVT= ΣTΣVT= ΛVT,which as the product of invertible matrices is invertible. Thus,dXi=1aiei= (ΛVT)−1Λ−1AT(mF− mM)CdXi=1aiei= C(Λ2VT)−1AT(mF− mM)w = C(Λ2VT)−1AT(mF− mM).We therefore have the following algorithm for finding w:1. Define C ∈ RN2×d: For 1 ≤ i ≤ d, the ithcolumn is the ithelement of F ∪M.2. Compute B = CTC ∈ Rd×d.3. Find the eigenvalues and eigenvectors of B. Store the eigenvalues as the diagonal entriesin Λ ∈ Rd×dand the (normalized) eigenvectors as the columns of V ∈ Rd×d.4. Define A ∈ RN2×d: For 1 ≤ i ≤ d, the ithcolumn is√λikCeik2Cei,where eiis the ithcolumn of V and λiis the (i, i)thentry of Λ.5. Compute y = AT(mF− mM) ∈ Rd.6. Solve (Λ2VT)z = y for z ∈ Rd. The matrix Λ2VTis d × d and nonsingular, so thisshould be computationally inexpensive.7. Compute w = Cz. Rescale if