sparse tucker factorisation with orthogonality

[renjithravindran]

Hi there, this certainly looks like a very interesting project!
I wanted to know if FunFact can do tucker decomposition of sparse tensors with orthogonality constraints on the factor matrices?

Thanks
Renjith

[yhtang]

Hi Renjith,

We can do Tucker with orthogonality constraints on dense target tensors out of the box. Regarding sparse tensors, I believe this is within reach using FunFact with the PyTorch backend, which supports sparse tensors in COO format. That said, could you please let me know

• Is there an estimate on the size of the target sparse tensor? What is the fill ratio (percentage of non-zero entries)?
• Are the factor matrices dense or sparse?
• What is the desired accuracy of the factorization?

Please also feel free to share any further details or thoughts that you might have. Thanks!

Yu-Hang

[renjithravindran]

Hi Yu-Hang

I am considering tensors of size like 50K*50K*10 with say more than 90% sparsity.
The factor matrices are dense with an optional sparse core tensor.
And say less than 50% reconstruction error.

Actually I have been looking at adding orthogonality constraint for tucker.
I checked out a few projects on pytorch but none seems to work out of box for tensors of size that is of interest to me.
geotorch
fastH

Exp Maps and the whole Lie theory is very elegant but cant be made to work for large tensors.
Householder seems to hold some promise but fastH seems to fail on large tensors too.

How does FunFact implement orthogonality constraint?
Would it work for large tensors?

Thanks
Renjith

[yhtang]

Good question. FunFact does not really implement 'hard' constraints, but rather just imposes 'soft' penalty terms. This seems to work for our quantum compilation example, where we expect the factor tensors to be unitary.

That said, is the problem here mainly about scaling? How well do the existing packages solve the "Tucker+orthogonal factors" problem for smaller target tensors?

[renjithravindran]

Yes it is a problem of scale.
Both the packages I tried, failed with out-of-memory errors.
The developer/author of GeoTorch said that it was expected for tensors of that size with Exp Map.
And suggested I try my luck with householder technique.

The problem with householder is that it isn't naturally parallel in nature, so is inefficient on GPUs.
The fastH package claims to make things go more parallel and hence faster on GPUs.
But even fastH gave me OOM error.

I tried soft constraints via a orthogonality regularization term.
It kinda gets the gram matrix to near identity but that wasn't giving me the results expected from the factor matrices.
So I concluded soft constraints aren't good enough for my problem!

Tensorly works, but it expensive in terms of RAM (more than 80GB) and CPU time.
Also I need a sparse core tensor, for a subsequent work, to prevent arbitrary rotations that the core/factors pick up.
But tensorly doesn't let one do that, so I thought its best done with gradient descent and autoGrad.
But the orthogonality part has got me stuck.
Anyways, now I have to get my hands dirty with houselder/fastH and see if I can fix the OOM somehow!
As of now I am busy writing-up the paper that gets the work done with tensorly.
But I am not very happy with it, as not everyone can use it due to the RAM requirements.
Also my next piece of work (requiring a sparse core tensor) can't even be solved by tensorly.

About your second question, I haven't tried these packages on smaller tensors.
They mostly would work I suppose, haha.
They provide orthogonality constraints for pytorch variables, mostly targeted at machine learning applications.

Let me know if hard constraints for orthogonality is something FunFact would be interested in.
BTW, my application for tensor decomposition is in Natural Language Processing.

Thanks
Renjith