Compute generalised eigenvectors

Cesare_Corrado · October 5, 2022, 3:48pm

Hi,
I wonder if it is possible to use TensorFlow also to compute generalised eigenvectors of the following (discretised Laplace Beltrami) problem:

Kv=l M v
where K and M are two symmetric matrices.

the tf.linalg.eig function seems computing the eigenvectors only for M=Id

Thanks,

Cesare

lgusm · October 12, 2022, 8:57am

maybe @markdaoust can help here

Snow_Summer · October 14, 2022, 9:42am

You need to write it by hand. Here is my code for it (see Numerical Recipes section 11.0.5), and if you want to use it you need to keep A and B Hermitian matrices and test it:

def generalized_eigen(A, B, eigvals_high_to_low=True):
    # see NR section 11.0.5
    # L is a lower triangular matrix from the Cholesky decomposition of B
    L = tf.linalg.cholesky(B)
    # solve Y * L^T = A by a workaround
    # if https://github.com/tensorflow/tensorflow/issues/55371 is solved then this can be simplified
    Y = tf.transpose(tf.linalg.triangular_solve(L, tf.transpose(A)))
    # solve L * C = Y
    C = tf.linalg.triangular_solve(L, Y)
    # solve the equivalent eigenvalue problem
    e, v = tf.linalg.eigh(C)
    # reverse the sorting order to non-increasing
    e_rev = tf.reverse(e, axis=[-1])
    v_rev = tf.reverse(v, axis=[-1])
    e = tf.cond(eigvals_high_to_low, lambda: e_rev, lambda: e)
    v = tf.cond(eigvals_high_to_low, lambda: v_rev, lambda: v)
    # e = tf.reverse(e, axis=[-1])
    # v = tf.reverse(v, axis=[-1])
    # solve L^T * x = v, where x is the eigenvectors of the original problem
    v = tf.linalg.triangular_solve(tf.transpose(L), v, lower=False)
    # # normalize the eigenvectors
    # v = tf.math.l2_normalize(v, axis=0)
    return e, v

Cesare_Corrado · November 8, 2022, 7:53pm

Thanks.
Does it work also for sparse tensors? Or there is something more efficient?

Snow_Summer · November 8, 2022, 8:10pm

I have no knowledge about sparse tensors since I don’t use it in my case.
As for the efficiency, it depends on what you need. Do you think it is inefficient?
In the actual calculation of loss I don’t use the above routine, since I just need a sum of generalized eigenvalues, so instead, I compute the trace of pseudoinverse(B)*A (you can refer to the math proof in linear algebra - Proof that the trace of a matrix is the sum of its eigenvalues - Mathematics Stack Exchange). Do you need both exactly both eigenvectors and eigenvalues in optimization?

Cesare_Corrado · November 9, 2022, 11:33am

Yes, I need both eigenvectors and eigenvalues (not all of them but a subset; says the first 100).
I’m using sparse tensors as I’m using sparse matrices possibly with large sizes.
The function works if I convert first the tensors to dense (tf.sparse.to_dense(A),tf.sparse.to_dense(B)); however, if matrices have large size, this might fill the GPU memory quite quickly.
I wonder if something exists under TensorFlow that works like linalg.eigs of scipy sparse:

https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.eigs.html

Snow_Summer · December 21, 2022, 9:10am

Unfortunately this is not implemented yet:

github.com/tensorflow/tensorflow

[Feature Request] Support Sparse Tensors in tf.linalg operations

opened 01:32PM - 01 Apr 19 UTC

suyash

type:feature comp:ops

<em>Please make sure that this is a feature request. As per our [GitHub Policy](…https://github.com/tensorflow/tensorflow/blob/master/ISSUES.md), we only address code/doc bugs, performance issues, feature requests and build/installation issues on GitHub. tag:feature_template</em> **System information** - TensorFlow version (you are using): 2.0.0a0 - Are you willing to contribute it (Yes/No): Maybe, if there are any pointers on how to go about implementing something like this. **Describe the feature and the current behavior/state.** Currently the `tf.linalg` operations seem to only support dense tensors. I have verified `tf.linalg.solve`. Consider the following variables ``` A = tf.sparse.SparseTensor( indices=[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]], values=[3., 2., -1., 2., -2., 4., -1., 0.5, -1.], dense_shape=(3, 3) ) b = tf.sparse.SparseTensor( indices=[[0, 0], [1, 0], [2, 0]], values=[-1., 2., 0.], dense_shape=(3, 1) ) ``` now if I do ``` tf.linalg.solve(A, b) ``` this errors out with ``` ValueError: Attempt to convert a value (<tensorflow.python.framework.sparse_tensor.SparseTensor object at 0x7f28a1e3fc50>) with an unsupported type (<class 'tensorflow.python.framework.sparse_tensor.SparseTensor'>) to a Tensor. ``` However, if I do ``` tf.linalg.solve(tf.sparse.to_dense(A), tf.sparse.to_dense(b)) ``` it works, giving ``` <tf.Tensor: id=11, shape=(3, 1), dtype=float32, numpy= array([[-1.0000006], [ 2.0000014], [ 2.0000012]], dtype=float32)> ``` which is roughly the correct answer. Example taken from the [scipy sparse matrix factorized](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.factorized.html) documentation. **Will this change the current api? How?** Instead of erroring out, the `linalg` operations will work for sparse inputs just as well as for dense inputs. **Who will benefit with this feature?** I came across this while implementing [NVIDIA's FastPhotoStyle](https://github.com/NVIDIA/FastPhotoStyle) in TensorFlow 2.0 + Keras. The algorithm essentially has 2 steps, - A `PhotoWCT` transformation that is `WCT` but uses maxpooling argvalues as unpooling masks - A Photorealistic smoothing step that restores geometric artifacts for objects distorted using regular style transform - An additional post processing step that applies a GPU based smoothing filter for further reducing structural defects The NVIDIA implementation provides a [`photo_wct` net implementation in PyTorch](https://github.com/NVIDIA/FastPhotoStyle/blob/master/photo_wct.py). However for the second step, [a CPU implementation in scipy is used](https://github.com/NVIDIA/FastPhotoStyle/blob/master/photo_smooth.py). The second step essentially solves a closed form system of equations. Consider [line 48](https://github.com/NVIDIA/FastPhotoStyle/blob/master/photo_smooth.py#L48), what it is essentially doing is creating a diagonal matrix of size (width x height) of the image. So for a 512x512 image, in dense form it will have to create a matrix of 2^36 floats. The matrix is later used to solve a system of equations (https://github.com/NVIDIA/FastPhotoStyle/blob/master/photo_smooth.py#L52). 2^36 tf.float32 values will occupy 2^8 = 256GB of memory, which will definitely overflow. Ideally, I should be able to work with tensorflow's `linalg` module just the same as the scipy implementation. An additional flexibility with TensorFlow is that it will place operations on GPUs automatically. Additionally, I can put it in a keras `Lambda` layer to add it to a model. **Any Other info.** No

On the other hand, I have checked the pytorch documentation, and the torch.lobpcg should be exactly what you want as you mentioned the “first N eigenvalues and eigenvectors”, but it does not support backward propagation (see the warning in the following link) for sparse tensor yet:
https://pytorch.org/docs/stable/generated/torch.lobpcg.html
So, what you need may not have a good solution.

Cesare_Corrado · January 12, 2023, 5:50pm

Thanks.
Concerning linear algebra (the feature request you posted), I also tried to implement the conjugate gradient for sparse tensors to invert matrices: It works but is very slow if compared with scipy. I have no idea why.