0
$\begingroup$

I am wondering whether there are some formulas that compute matrix eigenvalues, determinant, rank, etc. directly from its vectorized representation.

More formally: suppose $\bf S \in \mathbb{S}^N$, i.e. square and symmetric. We can represent any matrix with its vectorized form $\bf s= \operatorname{vec(\bf S)} \in \mathbb{R}^{N^2}$, i.e. by storing all its entries in a vector. At this point we can perform operations involving $\bf S$, by equivalently using $\bf s$. Simple example: $$\operatorname{trace}(\bf A^\top \bf S) = \sum_{i,j}A_{ij} S_{ij}= \operatorname{vec(\bf A)}^\top \operatorname{vec(\bf S)}= \bf a ^\top \bf s$$

This makes sense clearly.

Question 1: My first question stems from the fact that we have clearly the same information in $\bf s$ as in $\bf S$, we are not losing anything if not the structure. Can we then compute, say, the eigenvalues of $\bf S$ from $\bf s$ without reshaping it? At the end, they are function of the entries of $\bf S$.

Question 2: If the answer to the above question is yes, then another fundamental question is whether we can perform the same operation in the half-vectorization space of the matrix, i.e. the vector storing only its lower (or upper) triangular part, for a symmetric matrix. Again, we are not losing any information.

An affirmative answer to the above question is important, for instance, in algorithms where the use of vectors reduces the dimensionality of the problem at hand, but where matrix properties are necessary. Thank you

EDIT: to make the context more clear. I am implementing an iterative algorithm working with the independent variables of the matrix only. I need to perform an SVD to shrink the singular values at every iteration. I am wondering whether I can perform such operation without reshaping the matrix and then reshape back to a vector.

$\endgroup$
8
  • $\begingroup$ Reshaping the matrix is not expensive, it is essentially free in most languages. Computing the SVD can be expensive. An Eigenvalue Decomposition (EVD) can be a bit (30%) faster for symmetric matrices. But if you require all of those singular values, then you must pay the computational price. The library routines for SVD are very mature; I doubt you'll be able to improve upon them using half-vec tricks. $\endgroup$
    – greg
    Feb 17, 2021 at 16:52
  • $\begingroup$ Thanks for your answer. Ok, but what about memory? Having a $N(N-1)/2$ vector instead of a $N^2$ matrix can in many cases make a difference, although it's nor order of magnitudes. But if such solution by working in the half-vec space would exists, the code itself would be more clean without all these lifting.. $\endgroup$
    – yes
    Feb 17, 2021 at 17:49
  • $\begingroup$ Yes, you will save space storing the matrix in compressed form. And you can do simple arithmetic (addition, multiplication) using the compact form. But in order to calculate the singular values you'll need to pass the full matrix to the SVD (or EVD) subroutine. If your laptop can't handle it, it doesn't cost that much to spin up an Amazon/AWS instance for a few minutes. $\endgroup$
    – greg
    Feb 17, 2021 at 18:30
  • $\begingroup$ True, that may be an option as well. So the answer to my question I guess is: " no, you cannot compute eigenvalues (end eigenvectors) without reshaping". Is that correct? In that case, it may be interesting to check. If we write down the Hessian of a function in the half-vec space, you most likely end up with a Kronecker product of two matrices of dimension $N^2$, hence requiring $N^4$ memory-side ($X \otimes X$). Being able to perform operation directly in the half-vec without reshaping may avoid such issues. Can we half-vectorize it again being symmetric? $\endgroup$
    – yes
    Feb 18, 2021 at 15:33
  • 1
    $\begingroup$ Nope, I was thinking of the standard duplication matrix but the equations I wrote are for a third-order duplication tensor. Anyway, the point of the exercise was to estimate how much memory could be saved (roughly a factor of 4). But the implementation gets so tricky that you're better off using standard linear algebra and a big AWS machine. $\endgroup$
    – greg
    Feb 18, 2021 at 19:54

1 Answer 1

1
$\begingroup$

As you note, the same information is there in either representation, so any property can be computed from either representation.

You are asking about whether there are efficiencies to be had choosing one representation over the other. I think the answer is "it depends". In algorithm design and implementation there are always tradeoffs to be made between work done on the data structure and work done in the procedural code. The balance will be different in different computations.

$\endgroup$
8
  • $\begingroup$ I need to compute an SVD for instance, and threshold the negative eigenvalues. Reshaping the matrix and compute the SVD is expensive. I am wondering whether I can manipulate directly the vector for instance $\endgroup$
    – yes
    Feb 15, 2021 at 16:49
  • 1
    $\begingroup$ That's a particular algorithm question, not the general one you asked here. I suspect that SVD and eigenvalue calculations have been well explored and that the most efficient algorithms are in the literature and implemented. I see several in a search for svd calclations. $\endgroup$ Feb 15, 2021 at 16:54
  • $\begingroup$ This discussion is pointless, as the compiler will anyway reshape the matrices in vectors. $\endgroup$
    – user65203
    Feb 15, 2021 at 16:59
  • $\begingroup$ @YvesDaoust I more or less agree that the discussion is pointless, but not quite for the same reason. The compiler's reshaping may not be the most efficient for algorithm access to the elements, which might be improved by deciding the reshaping at the program level. $\endgroup$ Feb 15, 2021 at 17:01
  • $\begingroup$ @EthanBolker: do you have any example in mind ? This would only work smoothly for row-by-row processing, which is pretty rare in matrix computation. First counter-example is matrix multiplication (or just matrix transposition). $\endgroup$
    – user65203
    Feb 15, 2021 at 17:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .