\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}