Thumbnail
Access Restriction
Open

Author Weinberger, Kilian Q. ♦ Sha, Fei ♦ Zhu, Qihui ♦ Saul, Lawrence K.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Matrix Factorization ♦ Graph Laplacian Regularization ♦ Con-structing Semidefinite Program ♦ Largescale Semidefinite Programming ♦ Graph Laplacian ♦ Matrix Variable ♦ High Variance ♦ Many Result ♦ Matrix Factorization Yield ♦ Low Dimensional Representation ♦ Sdps Cannot ♦ Common Solution ♦ Conjugate Gradient De-scent ♦ Many Area ♦ Bottom Eigenvectors ♦ Good Approximation ♦ Maximal Trace Solution ♦ High Dimensional Data ♦ Local Distance Constraint ♦ Original Problem ♦ Low Rank Solution ♦ Convex Optimization ♦ Large Problem ♦ Large Scale Sensor Network
Description In many areas of science and engineering, the problem arises how to discover low dimensional representations of high dimensional data. Recently, a number of re-searchers have converged on common solutions to this problem using methods from convex optimization. In particular, many results have been obtained by con-structing semidefinite programs (SDPs) with low rank solutions. While the rank of matrix variables in SDPs cannot be directly constrained, it has been observed that low rank solutions emerge naturally by computing high variance or maximal trace solutions that respect local distance constraints. In this paper, we show how to solve very large problems of this type by a matrix factorization that leads to much smaller SDPs than those previously studied. The matrix factorization is de-rived by expanding the solution of the original problem in terms of the bottom eigenvectors of a graph Laplacian. The smaller SDPs obtained from this matrix factorization yield very good approximations to solutions of the original problem. Moreover, these approximations can be further refined by conjugate gradient de-scent. We illustrate the approach on localization in large scale sensor networks, where optimizations involving tens of thousands of nodes can be solved in just a few minutes. 1
In NIPS
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2006-01-01