What’s the Name of This Matrix Decomposition?

I was talking with colleagues about link prediction in directed networks and we came up with the following problem:  Given a square, asymmetric matrix A, find a decomposition

A = U X U¯¹

such that U is orthogonal, and X is not necessarily diagonal.  The idea is to introduce asymmetry into the decomposition by making X asymmetric, and therefore non-diagonal.  If the decomposition is of low-rank, i.e. U is a n-by-r matrix and X a r-by-r matrix with r ≪ n, then we can then compute powers of A very efficiently by computing powers of X, and thus compute any power of A. The result is that we can implement link prediction in directed graph efficiently.

Do you have an idea how to solve this?  There doesn’t seem to be a common name for this kind of decomposition– If you know anything, please comment!

Background

Given a network with n nodes, we can represent it as an n-by-n matrix A called the adjacency matrix. The power A^k can then be used to count the number of paths from any node to any other node.  Since in practice A is very large, we can’t just compute powers of it by matrix multiplication.  Instead, one must use matrix decompositions.  For instance, if A is symmetric, then it has an eigenvalue decomposition

A = U Λ U^T

This can be exploited to compute powers of A by using the fact that in the eigenvalue decomposition, U is an orthogonal matrix (meaning that U^T = U¯¹) and that Λ is diagonal (meaning that its powers can be computed by computing the powers of its diagonal elements):

A^k = U Λ U^T U Λ U^T … U Λ U^T = U Λ^k U^T

The trick works because U^T U equals the identity matrix.  If the graph is directed however, then A is asymmetric and this trick does not work! A related idea is to use the singular value decomposition, which is defined for all matrices:

A = U Σ V^T

This is defined for asymmetric matrices, but the trick from above does not work, because V^T U will not simplify away.  Any ideas?

ADDENDUM

Thanks for Tamara G. Kolda for giving the solution:  The decomposition is called DEDICOM, which stands for Decomposition into Directional Components.  See these two papers:

Models for Analysis of Asymmetrical Relationships Among N Objects or Stimuli, Richard Harshman, First Joint
Meeting of the Psychometric Society and the Society for
Mathematical Psychology, 1978.

Here’s a 3-way version of it, i.e. for 3-tensors:

Temporal analysis of semantic graphs using ASALSAN, Brett Bader, Richard Harshman & Tamara G. Kolda, ICDM 2007.

ADDENDUM (DECEMBER 2012)

I wrote a paper about this decomposition and its application to link prediction in directed networks at the International Conference on Data Mining 2012:

Predicting Directed Links using Nondiagonal Matrix Decomposition, Jérôme Kunegis & Jörg Fliege, ICDM 2012.