\documentclass{article} \begin{document} \title{Symmetric rank-revealing factorizations} \author{P. C. Hansen \\ Department of Mathematical Modeling, \\ Danish Technical University, \\ DK-2800 Lyngby, Denmark, \\ e-mail: pch@imm.dtu.dk \and P. Y. Yalamov \\ Center of Applied Mathematics and Informatics, \\ University of Rousse, 7017 Rousse, Bulgaria, \\ e-mail: yalamov@ami.ru.acad.bg} \date{} \maketitle Matrix rank-revealing factorizations are useful in many applications (for example for obtaining a regularized solution in signal and image processing). A number of rank-revealing factorizations have been presented in the existing literature. The most famous one is the Singular Value Decomposition \cite{golub} but it is rather expensive to compute. In the last decade new techniques have been developed which are faster. These are the Rank Revealing QR decomposition (RRQR) \cite{chan}, and the URV (ULV) triangular decompositions \cite{stewart}. All these approaches are developed for general matrices which do not utilize the special structure of the matrix (if any). In some applications the matrix of interest is symmetric. So, it would be appropriate if we can use the symmetric structure in order to propose faster rank-revealing factorization algorithms and retain symmetry in the reduced-rank matrix approximation. When in addition the matrix is also positive definite the Cholesky algorithm \cite{golub} is the tool at hand for computing a fast decomposition. But if the matrix is semidefinite, or indefinite, then it is known that the Cholesky algorithm can break down (or produce completely wrong results in the presence of roundoff errors). Also, even if the Cholesky decomposition is successful we do not know whether it is rank-revealing. To the knowledge of the authors there is only one reference \cite{luk} in which symmetry is exploited to produce a rank-revealing factorization for a Toeplitz matrix. But it suffers from the drawback that pivoting is undesirable because it spoils the Toeplitz structure. Thus the algorithm can be very unstable. In this talk we discuss methods for computing the rank-revealing factorization of a symmetric matrix (it can be semidefinite, or indefinite). The methods are based on the $LDL^{T}$ factorization with pivoting, where $L$ is unitlower triangular, and $D$ is block diagonal with $1\times 1$, or $2\times 2$ blocks on the diagonal. We also make use of the RRQR decomposition as a basic "tool". We present conditions under which the factorization is rank-revealing. Bounds on the smallest singular values and the corresponding subspaces are given as well. Numerical evidence illustrates the theoretical conclusions. \begin{thebibliography}{1} \bibitem{chan} T. F. Chan, Rank revealing QR factorizations, Lin. Alg. Appl. 88(1987), pp. 67--82. \bibitem{golub} G. H. Golub and C. F. van Loan, Matrix Computations, John Hopkins University Press, 3rd edition, 1996. \bibitem{luk} F. T. Luk and S. Qiao, A symmetric rank-revealing Toeplitz matrix decomposition, J. VLSI Signal Proc. 14(1996), pp. 19--28. \bibitem{stewart} G. W. Stewart, An updating algorithm for subspace tracking, IEEE Trans. Signal Proc. 40(1992), pp. 1535--1541. \end{thebibliography} \end{document} 