Least square solution based on the pseudoinverse solved efficiently with singular value decomposition

Hi apologies it's hard to type out the problem,

I have a lecture slide on neural networks. It says the fitting error gives the matrix:

N by M matrix of thi's multiplied by Mx1 weights minus Nx1 outputs (ys)

The Euclidean distance of this entire function is then found. Thi is a function, given at the bottom, w are the corresponding weights and y is the network output.

Following this the slide says "The above minimisation problem is usually solved using the least squares solution based on the pseudoinverse:

w = thi y thi has + above indicating pseudoinverse. "This pseudoinverse is efficiently solved using the singular value decomposition (SVD) techniques".

thi+ = (limit (thi_transpose * thi + lambda * Identity_Matrix)^(-1)) * thi_transpose

The limit is as lamba tends to zero. Lambda is a user-defined regularisation parameter, whereby 0 = no smoothness and infinity gives unreliable results.

I've been reading for ages and still dont understand this last line at all. Please could someone go through an example, or how to solve this? (use what values of thi u want)

Extra information I don't know if it's useful:

Thi(x) = exp( - euc_dist(x-ci) / 2*gamma_squared)

x = network input, c = centre of neuron, gamma = width.

Summary

I need to use the least square solution based on the pseudoinverse of an NxM thi matrix multiplied by Nx1 weight matrix minus Nx1 output matrix to find the Nx1 weight matrix.

w = pseudo_inverse_thi * output vector

where pseudo_inverse_thi = limit equation above

The SVD is somehow used to accomplish this. If I make no sense, I apologise, I'm utterly lost.

• You can start by reading the Wikipedia article on SVD. Calculating the Moore-Penrose pseudoinverse is the first thing listed in the applications section. – Nathan Reed Apr 4 '13 at 23:28
• It sounds like you need to compute a least squares solution to $Ax = b$. There are various ways to do this, and one popular method uses the SVD. A less sophisticated approach would be to solve the "normal equations" $A^T Ax = A^T b$ using a method like Gaussian elimination. However, depending on what software you're using, you might not need to worry about the details of finding a least squares solution. For example, in Matlab you can just type x = A \ b ; – littleO Jun 19 '14 at 23:12
• About "typing out the problem", you can look here: MathJax basic tutorial and quick reference. – fonini May 9 '16 at 0:26

This is just the standard approach to solving linear least-squares problems; I suppose that's why the author glossed over it.

From a theoretical point of view, the equations that arise in a least-squares problem can be solved neatly by using a matrix "pseudo-inverse". This is just like the way you use a matrix inverse to "solve" a traditional set of linear equations. But, in both cases, you're not really "solving" the equations -- the matrix inverses just give you a nice tidy way to write the solutions in a theoretical description.

But, as everyone knows, the computational techniques are not the same as the theoretical ones. To compute the solution of a system of linear equations, you would never compute a matrix inverse. And, similarly, to compute the solution of a least-squares problem, you would not compute the pseudo-inverse of the associated matrix. Instead, you would compute its SVD. Again, a completely standard approach.

There is a fairly readable account of all this in these slides.

Or, even better, maybe, look at this wikipedia article. Section 4 talks about computational techniques, including SVD techniques.

• Thanks, I'm still confused though. If I dont compute the matrix then I dont understand how I get any of the U sigma or I parts. Would it be possible to go through an example? I've been trying to get my head around it but I'm going round in circles – Fred Johnson Apr 5 '13 at 20:00
• Sorry for the delay -- didn't see your comment until today. You do compute the matrix. But you don't compute its inverse. Matrix inverses are just a neat way to write down the theory. In practice, inverting matrices is usually a bad way to solve computational problems. – bubba Apr 30 '13 at 11:17
• The link is dead. You may replace it by - docs.google.com/viewer?url=https://github.com/RoyiAvital/…. Something I rote once on SVD. – Royi Sep 8 '17 at 19:07