Comments (4)
Is there a bound on the value of rank for a given tensor?
Hi! Here I am offering you my findings on this problem: The parameter R you referred to is the number of components, i.e. rank-one tensors, you would like to have in the result of your CP decomposition. In the given reference of randomised_parafac()
, (Casey Battaglino, Grey Ballard and Tamara G. Kolda, "A Practical Randomized CP Tensor Decomposition"), section 3.1, there was a discussion on the smallest number of rank-one tensors in an exact CP decomposition, i.e. the tensor rank. Here I am citing a few relevant points:
- There is no straightforward algorithm to determine the rank of a specific tensor. In fact, the problem is NP-hard.
- In practice, the rank of a tensor is determined numerically by fitting various rank-R CP models. (In section 3.4) Ideally, if the data is noise-free, and we have a procedure for calculating CP with a given number of components, then we can do that for R=1,2,3… and stop at the first value of R that gives a fit of 100%. However, there are many problems with this procedure. … When the data are noisy (as is frequently the case), then fit alone cannot determine the rank in any case; …
- ALS, today's workhorse method to compute CP at a given R, can take many iterations to converge, and is not guaranteed to converge to the global minimum or even a stationary point. The author also summarized typical ranks of three-way tensors over R space with or without frontal slice symmetry.
(Btw, I checked the arXiv paper again today and could not find the tensor rank section any more. Not sure why but I am trying to find the version I read a few days ago.)
Regarding the singular matrix error, specifically
factor = tl.transpose(tl.solve(pseudo_inverse, factor))
In numpy/linalg/linalg.py
def solve(a, b):
"""
Solve a linear matrix equation, or system of linear scalar equations.
Computes the "exact" solution, `x`, of the well-determined, i.e., full
rank, linear matrix equation `ax = b`.
…
"""
It seems that the singular matrix error occurs when a
in ax=b
is not invertible, which in this case means pseudo_inverse
is not invertible. We confirm this by inspecting the determinant of pseudo_inverse
:
############## START
R = 2
############## ITERATE
======== iteration 0
------------- mode 0
det of pseudo_inverse: 4.791666666666669
------------- mode 1
det of pseudo_inverse: 4.397817528932697e-29
------------- mode 2
det of pseudo_inverse: 0.0
Traceback (most recent call last):
...
numpy.linalg.LinAlgError: Singular matrix
Inspecting the calculation steps:
711 kr_prod, indices_list = sample_khatri_rao(
712 factors, n_samples, skip_matrix=mode, random_state=rng
713 )
…
724 pseudo_inverse = tl.dot(tl.transpose(kr_prod), kr_prod)
There can be multiple causes for det(pseudo_inverse) = 0
, analytical or numerical.
Analytically, kr-prod
is the sampled khatri-rao product of size (n_samples, R), and pseudo_inverse = tl.dot(tl.transpose(kr_prod), kr_prod)
is of size (R, R). If we want pseudo_inverse
to be invertible, kr_prod
should have R non-zero eigenvalues.
Numerically, one possible reason is that column normalization of the updated factors is currently not implemented in randomised_parafac()
. I'm not sure why this step is skipped.
from tensorly.
chaoyihu is right about what the issues is here. I'll elaborate a bit further.
The issue is not with the choice of rank, but rather the choice of number of samples (n_samples
) which is the 3rd parameter in randomised_parafac
. In the ALS algorithm for CP decomposition, each step involves solving a highly overdetermined linear least squares problem, i.e., something of the form randomised_parafac
does is draw a subset of the rows in this linear system uniformly at random. The number of rows that are drawn is determined by n_samples
. When this is set to 1 as in your example, only a single row is drawn. When
To see why this is a problem, suppose randomised_parafac
solves this via the normal equations, i.e., by reformulating it to the problem of solving solve
function which can only handle full-rank problems, i.e., when n_samples
< rank
, this matrix will always be rank-deficient and solve
won't work.
In practice, since the sampling is done uniformly at random, even if n_samples
rank
, there's a chance that the system n_samples
to be quite a bit bigger than rank
.
As a side note, randomised_parafac
doesn't actually implement any of the methods by Battaglino et al. That paper uses randomized trigonometric transforms to first mix the rows before sampling. The way randomised_parafac
is implemented currently, it's easy to construct an adversarial example which breaks the method (which would give the kind of singular matrix error you noticed) with high likelihood even when a large number (say, half) of all rows are included in the linear least squares problems.
from tensorly.
@OsmanMalik thanks for the comment! Could you elaborate on the issue with the randomized parafac? Would be awesome if you are able to add a fix! :)
from tensorly.
@OsmanMalik thanks for the comment! Could you elaborate on the issue with the randomized parafac? Would be awesome if you are able to add a fix! :)
@JeanKossaifi Suppose for example that the design matrix
That's how the construction of the adversarial example goes. Of course, in practice things usually end up being a lot nicer than an adversarial example, so uniform sampling should work adequately and perform more closely to a sampler with theoretical guarantees like those based on leverage score sampling or fast trig transforms.
Would love to add a fix, but have limited time these days. Will take a stab if I find the time!
from tensorly.
Related Issues (20)
- Is there any t-product implementation code in tensorly?Thanks HOT 1
- More descriptive message when random PARAFAC2 rank is infeasible given shape HOT 1
- AssertionError: `tensorly.tt_tensor.validate_tt_rank` test HOT 1
- Tensor Conversion in TensorLy Does Not Preserve PyTorch Tensor dtype and device Attributes
- PARAFAC2 for missing data HOT 1
- Panel Dataset Time, Company, Feature HOT 1
- No attribute "device" when using Numpy backend HOT 6
- Remove MXNet from doc
- Parafac\parafac2 projection HOT 1
- Tensorly support float16/int8 HOT 2
- OOM issue HOT 6
- Question: CP decomposition of symmetric tensor with repeating factor matrix HOT 1
- How can I apply activation to each factor matrix? HOT 2
- Spiked tensor decomposition HOT 5
- code problems HOT 1
- SGD_Tukcer HOT 1
- tensorly version 0.8.0 parafrac does not run on GPU with pytorch backend HOT 1
- Normalizing factors in non-negative CP decomposition HOT 3
- about unfold HOT 7
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from tensorly.