Least Squares with Examples in Signal Processing1 x

1 Least Squares with Examples in Signal Processing1 The sum of Squares ' of x is denoted by kxk22 , , Ivan Selesnick March 7, 2013 NYU-Poly kxk22 =. X. |x(n)|2 = xT x. (3). These notes address (approximate) solutions to linear equations by Least n Squares . We deal with the easy' case wherein the system matrix is full The energy' of a vector x refers to kxk22 . rank. If the system matrix is rank deficient, then other methods are In these notes, it is assumed that all vectors and matrices are real-valued. needed, , QR decomposition, singular value decomposition, or the In the complex-valued case, the conjugate transpose should be used in place pseudo-inverse, [2, 3].

2 Of the transpose, etc. In these notes, Least Squares is illustrated by applying it to several basic problems in Signal processing: 2 Overdetermined equations 1. Linear prediction Consider the system of linear equations 2. Smoothing y = Hx. 3. Deconvolution If there is no solution to this system of equations, then the system is 4. System identification overdetermined'. This frequently happens when H is a tall' matrix (more rows than columns) with linearly independent columns. 5. Estimating missing data In this case, it is common to seek a solution x minimizing the energy of For the use of Least Squares in filter design, see [1].

3 The error: 1 Notation J(x) = ky Hxk22 . We denote vectors in lower-case bold, , Expanding J(x) gives . x1. J(x) = (y Hx)T (y Hx) (4). x2 .. x= .. (1) = yT y yT Hx xT HT y + xT HT Hx (5).. T T T T. xN = y y 2y Hx + x H Hx. (6). We denote matrices in upper-case bold. The transpose of a vector or matrix Note that each of the four terms in (5) are scalars. Note also that the scalar in indicated by a superscript T , , xT is the transpose of x. xT HT y is the transpose of the scalar yT Hx, and hence xT HT y = yT Hx. The notation kxk2 refers to the Euclidian length of the vector x, , Taking the derivative (see Appendix A), gives.

4 Q kxk2 = |x1 |2 + |x2 |2 + + |xN |2 . (2) J(x) = 2HT y + 2HT Hx x 1 For feedback/corrections, email Setting the derivative to zero, Matlab software to reproduce the Examples in these notes is available on the web or from the author.. Last edit: November 26, 2013 J(x) = 0 = HT Hx = HT y x 1. Let us assume that HT H is invertible. Then the solution is given by Set the derivatives to zero to get: x = (HT H) 1 HT y. x=. 1 T. H (11). 2. This is the Least Squares ' solution. y = Hx (12). 1. min ky Hxk22 = T. x = (H H) T. H y (7). x Plugging (11) into (12) gives In some situations, it is desirable to minimize the weighted square error, 1.

5 Y= HHT . , n wn rn2 where r is the residual, or error, r = y Hx, and wn are P. 2. positive weights. This corresponds to minimizing kW1/2 (y Hx)k22 where Let us assume HHT is invertible. Then W is the diagonal matrix, [W]n,n = wn . Using (7) gives = 2(HHT ) 1 y. (13). min kW1/2 (y Hx)k22 = x = (HT WH) 1 HT Wy (8). x where we have used the fact that W is symmetric. Plugging (13) into (11) gives the Least Squares ' solution: 3 Underdetermined equations x = HT (HHT ) 1 y. Consider the system of linear equations We can verify that x in this formula does in fact satisfy y = Hx by plugging y = Hx.

6 In: Hx = H HT (HHT ) 1 y = (HHT )(HHT ) 1 y = y . If there are many solutions, then the system is underdetermined'. This X. frequently happens when H is a wide' matrix (more columns than rows). with linearly independent rows. So, In this case, it is common to seek a solution x with minimum norm. That min kxk22 y = Hx = x = HT (HHT ) 1 y. (14). is, we would like to solve the optimization problem x min kxk22 (9) In some situations, it is desirable to minimize the weighted energy, , x P 2. n wn xn , where wn are positive weights.

7 This corresponds to minimizing such that y = Hx. (10). kW1/2 xk22 where W is the diagonal matrix, [W]n,n = wn . The derivation Minimization with constraints can be done with Lagrange multipliers. So, of the solution is similar, and gives define the Lagrangian: 1. min kW1/2 xk22 y = Hx = x = W 1 HT HW 1 HT y L(x, ) = kxk22 T. + (y Hx) x (15). Take the derivatives of the Lagrangian: This solution is also derived below, see (25). L(x) = 2x HT . x 4 Regularization In the overdetermined case, we minimized ky Hxk22 . In the underde- L(x) = y Hx termined case, we minimized kxk22.

8 Another approach is to minimize the 2. weighted sum: c1 ky Hxk22 + c2 kxk22 . The solution x depends on the Setting the derivative to zero, ratio c2 /c1 , not on c1 and c2 individually.. A common approach to obtain an inexact solution to a linear system is J(x) = 0 = HT Hx + AT Ax = HT y x to minimize the objective function: = (HT H + AT A) x = HT y J(x) = ky Hxk22 + kxk22 (16). So the solution is given by where > 0. Taking the derivative, we get x = (HT H + AT A) 1 HT y . J(x) = 2HT (Hx y) + 2 x x So, Setting the derivative to zero, min ky Hxk22 + kAxk22.

9 X (18). J(x) = 0 = HT Hx + x = HT y = x = (HT H + AT A) 1 HT y x = (HT H + I) x = HT y Note that if A is the identity matrix, then equation (18) becomes (17). So the solution is given by 6 Constrained Least Squares T 1 T. x = (H H + I) H y Constrained Least Squares refers to the problem of finding a Least Squares solution that exactly satisfies additional constraints. If the additional So, constraints are a set of linear equations, then the solution is obtained as min ky Hxk22 + kxk22 = x = (HT H + I) 1 HT y (17) follows. x The constrained Least Squares problem is of the form: This is referred to as diagonal loading' because a constant, , is added to the diagonal elements of HT H.

10 The approach also avoids the problem min ky Hxk22 (19). x of rank deficiency because HT H + I is invertible even if HT H is not. In such that Cx = b (20). addition, the solution (17) can be used in both cases: when H is tall and when H is wide. Define the Lagrangian, 5 Weighted regularization L(x, ) = ky Hxk22 + T (Cx b). A more general form of the regularized objective function (16) is: The derivatives are: J(x) = ky Hxk22 + kAxk22.. L(x) = 2HT (Hx y) + CT . where > 0. Taking the derivative, we get x . J(x) = 2HT (Hx y) + 2 AT Ax L(x) = Cx b x.