@article{berry1995ula, author = {Berry, M.W. and Dumais, S.T. and O'Brien, G.W.}, interhash = {500361a1ef20600fb86dc5c94c61d276}, intrahash = {f962590e6aa2ab97e21861051e705b9a}, journal = {SIAM REVIEW}, pages = {573--595}, publisher = {SIAM SOCIETY FOR INDUSTRIAL AND APPLIED}, title = {{Using Linear Algebra for Intelligent Information Retrieval}}, volume = 37, year = 1995 } @article{wall2003svd, author = {Wall, M.E. and Rechtsteiner, A. and Rocha, L.M.}, interhash = {6d300aa138c4770a2b0a1bb2b186cb38}, intrahash = {22b8f2dd4a39ec29d9f3383b001ba81b}, journal = {A Practical Approach to Microarray Data Analysis}, pages = {91--109}, publisher = {Springer}, title = {{Singular value decomposition and principal component analysis}}, year = 2003 } @unpublished{ranade:sus, author = {Ranade, A.G.}, interhash = {473e92f688426631dd9ccc7639a5e861}, intrahash = {9f7f1562631792a85f2dd5f5eefbcf4d}, title = {{Some uses of spectral methods}}, year = 2000 } @article{354398, abstract = {We discuss a multilinear generalization of the singular value decomposition. There is a strong analogy between several properties of the matrix and the higher-order tensor decomposition; uniqueness, link with the matrix eigenvalue decomposition, first-order perturbation effects, etc., are analyzed. We investigate how tensor symmetries affect the decomposition and propose a multilinear generalization of the symmetric eigenvalue decomposition for pair-wise symmetric tensors.}, address = {Philadelphia, PA, USA}, author = {Lathauwer, Lieven De and Moor, Bart De and Vandewalle, Joos}, doi = {http://dx.doi.org/10.1137/S0895479896305696}, interhash = {345c21b8420f7d9f83db12f440211715}, intrahash = {eff602c4bab6277525a861ffaf7ae297}, issn = {0895-4798}, journal = {SIAM J. Matrix Anal. Appl.}, number = 4, pages = {1253--1278}, publisher = {Society for Industrial and Applied Mathematics}, title = {A Multilinear Singular Value Decomposition}, url = {http://portal.acm.org/citation.cfm?id=354398}, volume = 21, year = 2000 } @article{Boley97principaldirection, abstract = {We propose a new algorithm capable of partitioning a set of documents or other samples based on an embedding in a high dimensional Euclidean space (i.e. in which every document is a vector of real numbers). The method is unusual in that it is divisive, as opposed to agglomerative, and operates by repeatedly splitting clusters into smaller clusters. The splits are not based on any distance or similarity measure. The documents are assembled in to a matrix which is very sparse. It is this sparsity that permits the algorithm to be very efficient. The performance of the method is illustrated with a set of text documents obtained from the World Wide Web. Some possible extensions are proposed for further investigation.}, author = {Boley, Daniel}, interhash = {281afd06bd3e21ec3ef212da4ec18ee0}, intrahash = {bca740460f14035af773f665887b6fa4}, journal = {Data Mining and Knowledge Discovery}, pages = {325--344}, title = {Principal Direction Divisive Partitioning}, volume = 2, year = 1997 } @inproceedings{Approximating2008Java, abstract = {In many social media applications, a small fraction of the members are highly linked while most are sparsely connected to the network. Such a skewed distribution is sometimes referred to as the"long tail". Popular applications like meme trackers and content aggregators mine for information from only the popular blogs located at the head of this curve. On the other hand, the long tail contains large volumes of interesting information and niches. The question we address in this work is how best to approximate the community membership of entities in the long tail using only a small percentage of the entire graph structure. Our technique utilizes basic linear algebra manipulations and spectral methods. It has the advantage of quickly and efficiently finding a reasonable approximation of the community structure of the overall network. Such a method has significant applications in blog analysis engines as well as social media monitoring tools in general. }, author = {Java, Akshay and Joshi, Anupam and FininBook, Tim}, booktitle = {Proceedings of the Second International Conference on Weblogs and Social Media(ICWSM 2008)}, date = {2008 Abstract:}, interhash = {ede357e110fee8803dc181d262f30087}, intrahash = {386f36679c111f30e37ced272d5b355c}, publisher = {AAAI Press}, title = {Approximating the Community Structure of the Long Tail}, url = {http://ebiquity.umbc.edu/paper/html/id/381/Approximating-the-Community-Structure-of-the-Long-Tail}, year = 2008 } @article{citeulike:2259488, author = {Golub, G. and Kahan, W.}, citeulike-article-id = {2259488}, citeulike-linkout-0 = {http://www.jstor.org/stable/2949777}, interhash = {8ef17e6b8c728315bba44c210313860a}, intrahash = {5b1464036866532034d1c0f4d7c417a2}, posted-at = {2008-02-13 12:56:34}, priority = {3}, title = {Calculating the Singular Values and Pseudo-Inverse of a Matrix}, url = {http://www.jstor.org/stable/2949777}, year = 1965 } @article{paige:197, author = {Paige, C. C.}, doi = {10.1137/0711019}, interhash = {e48832265f0709fd9f2ace01b30c784f}, intrahash = {b4613d688980df604dca04f8dc84d054}, journal = {SIAM Journal on Numerical Analysis}, number = 1, pages = {197-209}, publisher = {SIAM}, title = {Bidiagonalization of Matrices and Solution of Linear Equations}, url = {http://link.aip.org/link/?SNA/11/197/1}, volume = 11, year = 1974 } @article{g.1970singular, author = {Golub, G. and Reinsch, C. ER}, interhash = {1a71930d48eedf01c8aa40c79d8c05da}, intrahash = {382be4664216e3e93ef456b5dc49f067}, journal = {Numerische Mathematik}, month = {#apr#}, number = 5, pages = {403--420}, title = {Singular value decomposition and least squares solutions}, url = {http://dx.doi.org/10.1007/BF02163027}, volume = 14, year = 1970 } @article{Wilkinson1968409, author = {Wilkinson, J. H.}, doi = {DOI: 10.1016/0024-3795(68)90017-7}, interhash = {f2e096b15563937876e1722a1ecf5d09}, intrahash = {aa055d1c5f950b410f72d37f542f86ad}, issn = {0024-3795}, journal = {Linear Algebra and its Applications}, number = 3, pages = {409--420}, title = {Global convergene of tridiagonal QR algorithm with origin shifts}, url = {http://www.sciencedirect.com/science/article/B6V0R-45GWP7F-CH/2/615d5423f13c406c644a8ad9e8ead942}, volume = 1, year = 1968 } @article{Demmel90accuratesingular, abstract = {omputing the singular values of a bidiagonal matrix is the fin al phase of the standard algow rithm for the singular value decomposition of a general matrix. We present a new algorithm hich compu tes all the singular values of a bidiagonal matrix to high relative accuracy indepen- - p den t of their magn itudes. In contrast, the standard algorithm for bidiagonal matrices may com ute sm all singular values with no relative accuracy at all. Numerical experiments show that K the new algorithm is comparable in speed to the standard algorithm , and frequently faster. eywords: singular value decomposition , bidiagonal matrix, QR iteration 1 AMS(MOS) subject classifications: 65F20, 65G05, 65F35 . Introduction The standard algorithm for computing the singular value decomposition ( SVD ) of a gen1 eral real matrix A has two phases [7]: ) Compute orthogonal matrices P and Q such that B = P AQ is in bidiagonal form , i.e. 1 1 1 T 1 . 2 has nonzero en tries only on its diagonal and first su...}, author = {Demmel, James and Kahan, W.}, interhash = {175297e82f7c9ddfb8feb5b67abcfdd9}, intrahash = {16c2df1b40001454483df74547ce13c4}, journal = {SIAM J. Sci. Stat. Comput}, pages = {873--912}, title = {Accurate Singular Values of Bidiagonal Matrices}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3740}, volume = 11, year = 1990 } @techreport{Gu94efficientcomputation, abstract = {We present a new algorithm for computing the singular value decomposition (SVD) of a matrix. The algorithm is based on using divide-and-conquer to compute the SVD of a bidiagonal matrix. Compared to the previous algorithm (based on QR-iteration) the new algorithm is at least 9 times faster on bidiagonal matrices of dimension n = 400, when running on a DEC Alpha with optimized BLAS. The speedup increases with dimension n. For the dense singular value decomposition, the speedup ranges from 2.2 to 3.9 for n = 400. When used to solve dense, square linear least squares problems, the operation count drops from 12n 3 to 8 3 n 3 , and the speedup ranges from 2.3 to 3.8 for n = 400. This means using the SVD for the least squares problem averages only 4.8 times slower than using simple QR decomposition, whereas it used to be over 15 times slower. We show how to modify the old least squares solver based on the SVD with QR-iteration to attain slightly better speedup, at the cost of O(n 2 ...}, author = {Gu, Ming and Demmel, James and Dhillon, Inderjit}, interhash = {8e22d1a391144993bd779827c9c2c467}, intrahash = {24fc7de317c4d490c33f222193a6b8c5}, title = {Efficient Computation of the Singular Value Decomposition with Applications to Least Squares Problems}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.5864}, year = 1994 } @article{207452, abstract = {The authors present a stable and efficient divide-and-conquer algorithm for computing the singular value decomposition (SVD) of a lower bidiagonal matrix. Previous divide-and-conquer algorithms all suffer from a potential loss of orthogonality among the computed singular vectors unless extended precision arithmetic is used. A generalization that computes the SVD of a lower banded matrix is also presented.}, address = {Philadelphia, PA, USA}, author = {Gu, Ming and Eisenstat, Stanley C.}, doi = {http://dx.doi.org/10.1137/S0895479892242232}, interhash = {a03505f7371d60767e415bf03b30e239}, intrahash = {06e9746865d202d86e69479f5841b1f0}, issn = {0895-4798}, journal = {SIAM J. Matrix Anal. Appl.}, number = 1, pages = {79--92}, publisher = {Society for Industrial and Applied Mathematics}, title = {A Divide-and-Conquer Algorithm for the Bidiagonal SVD}, url = {http://portal.acm.org/citation.cfm?id=207440.207452}, volume = 16, year = 1995 } @article{1327974, abstract = {We describe the design and implementation of a new algorithm for computing the singular value decomposition (SVD) of a real bidiagonal matrix. This algorithm uses ideas developed by Grosser and Lang that extend Parlett’s and Dhillon’s multiple relatively robust representations (MRRR) algorithm for the tridiagonal symmetric eigenproblem. One key feature of our new implementation is that $k$ singular triplets can be computed using only $\mathcal{O}(nk)$ storage units and floating point operations, where $n$ is the dimension of the matrix. The algorithm will be made available as routine xBDSCR in the upcoming new release of the LAPACK library.}, address = {Philadelphia, PA, USA}, author = {Willems, Paul R. and Lang, Bruno and Vo\¨mel, Christof}, doi = {http://dx.doi.org/10.1137/050628301}, interhash = {52b9a6c03334206eba8bb52f15f0e738}, intrahash = {0ec95a4bca5e56d732f39620efddb921}, issn = {0895-4798}, journal = {SIAM J. Matrix Anal. Appl.}, number = 4, pages = {907--926}, publisher = {Society for Industrial and Applied Mathematics}, title = {Computing the Bidiagonal SVD Using Multiple Relatively Robust Representations}, url = {http://portal.acm.org/citation.cfm?id=1327974}, volume = 28, year = 2006 } @book{0898713560, asin = {0898713560}, author = {Lawson, Charles L. and Hanson, Richard J.}, dewey = {511.42}, ean = {9780898713565}, edition = {New edition}, interhash = {50dfdc5374514f626200bf1eac70e1ab}, intrahash = {a4b4ef55b6e8334375ad9ba4ffa5cc0b}, isbn = {0898713560}, publisher = {Society for Industrial Mathematics}, title = {Solving Least Squares Problems (Classics in Applied Mathematics)}, url = {http://www.amazon.de/Solving-Squares-Problems-Classics-Mathematics/dp/0898713560%3FSubscriptionId%3D192BW6DQ43CK9FN0ZGG2%26tag%3Dws%26linkCode%3Dxm2%26camp%3D2025%26creative%3D165953%26creativeASIN%3D0898713560}, year = 1987 } @article{hernandez2008robust, author = {HERNANDEZ, V. and ROMAN, J.E. and TOMAS, A.}, interhash = {c51989fb5e4fda373f21bcef4f3f0409}, intrahash = {5ab9b9c0c8edc22559bf852ef2b2729b}, journal = {Electronic Transactions on Numerical Analysis}, pages = {68--85}, title = {{A robust and efficient parallel SVD solver based on restarted Lanczos bidiagonalization}}, url = {http://scholar.google.de/scholar.bib?q=info:ndd8XEcM6icJ:scholar.google.com/&output=citation&hl=de&ct=citation&cd=0}, volume = 31, year = 2008 } @article{355946, abstract = { A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix
ACM Home Page
Please provide us with feedback. Feedback
A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix
Full text PdfPdf (977 KB)
Source ACM Transactions on Mathematical Software (TOMS) archive
Volume 7 ,  Issue 2  (June 1981) table of contents
Pages: 149 - 169  
Year of Publication: 1981
ISSN:0098-3500
Authors
Gene H. Golub  Department of Computer Science, Cornell University, Ithaca, NY
Franklin T. Luk  Department of Computer Science, Cornell University, Ithaca, NY
Michael L. Overton  Courant Institute of Mathematical Sciences, New York University, New York
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 11,   Downloads (12 Months): 80,   Citation Count: 2
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/355945.355946
What is a DOI?

REFERENCES
 
1
CULLUM, J. The simultaneous computation of a few algebraically largest and smallest elgenvalues of a large, sparse, symmetric matrix. Rep. RC 6827, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1977.
 
2
CULLUM, J., AND DONATH, W.E. A block Lanczos algorithm for computing the q algebraically largest eigenvalues and a corresponding eigenspace of large, sparse, real symmetric matmces. In Proc. 1974 IEEE Conf on Decas~on and Control, Phoenix, Ariz., 1974, pp. 505-509.
 
3
CULLUM, J., AND WILLOUGHBY, R.A. Computing singular values and corresponding singular vectors of large matrices by Lanczos tridiagonalization. Rep. RC 8200, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1980.
 
4
GENTLEMAN, W.M. Least squares computations by Givens transformations w~thout square roots. JIMA 12 (1973), 329-336.
 
5
GOLUB, G H, AND KAHAN, W Calculating the singular values and pseudo-inverse of a matrix. SIAM J. Numer Anal. 2 (1965), 205-224.
 
6
GOLUB, G.H., AND LUK, F T. Singular value decomposition: Apphcations and computations. ARO Rep. 77-1, in Trans. 22nd Conf. of Army Mathematw~ans, 1977, pp. 577-605.
 
7
 
8
GOLUB, G.H., AND REINSCH, C Singular value decomposition and least squares solutions. Numer. Math. 14 (1970), 403-420.
 
9
GOLUB, G H., AND UNDERWOOD, R. The block Lanczos method for computing elgenvalues. In Mathematical Software III, J.R. Rice (Ed.), Academic Press, New York, 1977, pp. 361-377.
 
10
LANCZOS, C L~near D~fferential Operators Van Nostrand, London, 1961.
 
11
 
12
ORTEGA, J.M. Numerical Analys~s: A Second Course Academic Press, New York, 1972.
 
13
PAIGE, C.C Bidiagonahzation of matrices and solution of hnear equations. SIAM J. Numer. Anal. 11 (1974), 197-209.
 
14
 
15
RUHE, A. Implementation aspects of band Lanczos algorithms for computation of elgenvalues of large sparse symmetric matrices Rep., Dep of Mathematics, Umv. California, San Diego, Feb. 1978.
 
16
RUTISHAUSER, H. On Jacobi rotation patterns. In Proc. Syrup. Applled Math, vol. 15, 1963, pp. 219-239.
 
17
STEWART, G W. Error and perturbation bounds for subspaces associated with certain elgenvalue problems. SIAM Rev 15 (1973), 727-764
 
18
 
19
 
20


Collaborative Colleagues:
Gene H. Golub: colleagues
Franklin T. Luk: colleagues
Michael L. Overton: colleagues

Peer to Peer - Readers of this Article have also read:

}, address = {New York, NY, USA}, author = {Golub, Gene H. and Luk, Franklin T. and Overton, Michael L.}, doi = {http://doi.acm.org/10.1145/355945.355946}, interhash = {b7d43137dfaa6351fc838c5c7a459a9f}, intrahash = {b6f719ab6d3027ab9967e80edd140959}, issn = {0098-3500}, journal = {ACM Trans. Math. Softw.}, number = 2, pages = {149--169}, publisher = {ACM}, title = {A Block Lanczos Method for Computing the Singular Values and Corresponding Singular Vectors of a Matrix}, url = {http://portal.acm.org/citation.cfm?id=355945.355946}, volume = 7, year = 1981 } @article{4767324, abstract = {A method for computing the partial singular value decomposition of a matrix is described. The method is appropriate to problems where the matrix is known to be of low rank and only the principal singular vectors are of interest. The technique is simple, easy to implement in integer arithmetic, and places modest memory requirements. The convergence properties of the algorithm are investigated analytically and by simulation.}, author = {Shlien, Seymour}, doi = {10.1109/TPAMI.1982.4767324}, interhash = {502eb8191e6eea1d2267894acb0ca433}, intrahash = {901e43c31a105c70f6b445c3fe7f14a6}, issn = {0162-8828}, journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on}, month = {Nov. }, number = 6, pages = {671-676}, title = {A Method for Computing the Partial Singular Value Decomposition}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=4767305&arnumber=4767324&count=23&index=16}, volume = {PAMI-4}, year = 1982 } @techreport{891601, abstract = {The truncated singular value decomposition (SVD) is considered as a method for regularization of ill-posed linear least squares problems. In particular, the truncated SVD solution is compared with the usual regularized solution. Necessary conditions are defined in which the two methods will yield similar results. This investigation suggests the truncated SVD as a favorable alternative to standard-form regularization in case of ill-conditioned matrices with a well-determined rank.}, address = {Stanford, CA, USA}, author = {Hansen, Per C}, interhash = {fb80b54fa51bf03e59980dc1e6a170e4}, intrahash = {ad995682545c5a74bcb4d273bc900800}, publisher = {Stanford University}, source = {http://www.ncstrl.org:8900/ncstrl/servlet/search?formname=detail\&id=oai%3Ancstrlh%3Astan%3ASTAN%2F%2FNA-M-86-36}, title = {The truncated SVD as a method for regularization}, url = {http://portal.acm.org/citation.cfm?id=891601}, year = 1986 } @article{78499, abstract = { Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations
ACM Home Page
Please provide us with feedback. Feedback
Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations
Source SIAM Journal on Scientific and Statistical Computing archive
Volume 11 ,  Issue 3  (May 1990) table of contents
Pages: 519 - 530  
Year of Publication: 1990
ISSN:0196-5204
Authors
Publisher
Society for Industrial and Applied Mathematics  Philadelphia, PA, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 1
Additional Information:

cited by   index terms   collaborative colleagues  

Tools and Actions: Review this Article  
DOI Bookmark: 10.1137/0911029


Collaborative Colleagues:
Tony F. Chan: colleagues
Per Christian Hansen: colleagues

}, address = {Philadelphia, PA, USA}, author = {Chan, Tony F. and Hansen, Per Christian}, doi = {http://dx.doi.org/10.1137/0911029}, interhash = {2b726f44b73d5f4344ec672b6ba15948}, intrahash = {2890d06aaac6e75f62984de8b61fb938}, issn = {0196-5204}, journal = {SIAM J. Sci. Stat. Comput.}, number = 3, pages = {519--530}, publisher = {Society for Industrial and Applied Mathematics}, title = {Computing truncated singular value decomposition least squares solutions by rank revealing QR-factorizations}, url = {http://portal.acm.org/citation.cfm?id=78499}, volume = 11, year = 1990 }