Applications of Linear (Matrix) Algebra

This piece is a collection from Prof. K's lecture notes on system theory.

1. Google page ranking is based on eigenvector. In summary, it is an eigenvector problem for a class of matrices known as stochastic matrices, ie row or col sum = 1. Using Perron-Frobenius theorem, we can find its stationary distribution, which is nothing but its dominant eigenvector. Sorting this vector gives the page-rank.
Article: http://www.ams.org/samplings/feature-column/fcarc-pagerank

2. How Netflix works? in heart it is a singular value decomposition problem. It all boils down to coming up with dim-red on a large - sparse user/item matrix
NewYork Times article: http://www.nytimes.com/2008/11/23/magazine/23Netflix-t.html?pagewanted=all&_r=0

3. LSI - latent semantic indexing is another beautiful thing - closely related instead of lexical matches, we find semantic matches again based on SVD.
SIAM paper link: http://lsirwww.epfl.ch/courses/dis/2003ws/papers/ut-cs-94-270.pdf

4.Music Genome project
http://courses.cs.washington.edu/courses/csep521/07wi/prj/michael.pdf

a variant of the CF algorithm.

 

Interior Point Method

This method is widely adopted in power system papers, whether it is a market equilibrium problem or it is an optimal power flow with stability constraint problem.

For convex optimization problem, IPM is exact approximation. The details of IPM can be found from Stephen Boyd's lecture ECE364a (Standford). Such approach is called central path approach since the starting point is from the feasible set and the search path is always located in the feasible region. Thus the name interior point method.

One basic objective for IPM is to convert inequality constraints into components of objective function using barrier or logarithmic function. Mathematically, this can be proved to be exact if one of the parameters keep increasing (t). IPM has been used to solve SDP problems and make numerical solving of linear matrix inequalities possible. This has facilitated robust control area.

There exist IPM solvers, such as the Matlab version fmincon. To be able to use the solvers, convexity has to be guaranteed. For many problems, to achieve convexity, we probably have to go through approximation steps. On the other hand, it is also a good idea to directly adopt IPM method for nonconvex problems. IPM, should be a good tool to tackle many problems.