7
$\begingroup$

(Posted this on math.stackexchange and cross.correlated over more than a week ago, but didn't get an answer, and this is a question in my research so this seems like it might have been the better place to ask...)

I'm wondering if there exists any higher-order SVD for dimensionality reduction. Note that I do not mean multilinear PCA, which operates on data tensors, but some form of SVD which can produce, say, a quadratic approximation of a dataset.

Intuitively, SVD takes in a set of vectors as a datset, and computes the ranked eigenvalues and eigenvectors which correspond to a reduced subspace and a "weight" representing their importance. Given a decomposition:

$$A = U\Sigma V^T$$

Where $A$ is a matrix where the columns are data vectors, the truncated matrix $U$ (keeping only the leftmost $n$ columns; call this truncated version $\mathcal{U}$) provides a reduced approximate basis for the original dataset $A$. However, this approximation is purely linear. It can thus be thought of as a linear approximation of the data on some $n$ reduced variable set. For a particular column of $a_i$ of $A$, $a_i \approx \mathcal{U} x_i$ for some dimensionality-reduced vector $x_i$.

I am wondering if it is possible to do something akin to a Taylor expansion here, and recover a higher-order approximation of the data. For example, for a quadratic system of order $n$, I'd like to generate the $\mathcal{U}$ matrix, but also a third-order tensor $\mathcal{W}$ such that a "quadratic" approximation of the data could be written, as, say:

$a_i \approx \mathcal{U} x_i + \frac{1}{2} x_i^T (\mathcal{W} ~ \vdots ~ x_i)$

where $\vdots$ is a tensor-vector contraction. (This is a form I made up now for discussion's sake; it is possible that the true form of some quadratic approximation is slightly different). Here, the best $x_i$ the quadratic approximation will be better than the linear one.

Ideally, I'd be searching for some general theory which would allow for arbitrary order approximation.

Is there any general established method for this (or something similar)? If so, is it tractable? If not, is there a mathematically grounded reason why not?

Improve this question
$\endgroup$
8
  • $\begingroup$ Suppose $A$ is "already" diagonal, with some entries "negligible"; what would be your next order approximation in this case? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Aug 5, 2018 at 8:09
  • $\begingroup$ If $A$ is "already" diagonal, then all the data can be described fully by linear components. The next order approximation tensor $\mathcal{W}$ would have to be $0$, no? $\endgroup$
    – user650261
    Commented Aug 5, 2018 at 18:53
  • 2
    $\begingroup$ Could you be more explicit about what you want to approximate? In the SVD case it holds that $a_i = Ae_i = U\Sigma V^T e_i = Ux_i$ with $x_i = \Sigma V^T e_i$ and this is exact… It is not clear to me, what you are trying to improve. $\endgroup$
    – Dirk
    Commented Aug 5, 2018 at 20:31
  • $\begingroup$ @Dirk the case is where you are keeping only the top $T$ components as in PCA. If I retain only the most significant components, then not all columns $a_i$ are completely described by the subspace spanned by $\mathcal{U}$ and you will only be able to construct some approximation to $A$ using that basis rather than a full reconstruction. Is there a way then to add this second order tensor term (or higher order term) to improve the approximation? $\endgroup$
    – user650261
    Commented Aug 6, 2018 at 3:57
  • $\begingroup$ And in what sense do you want to improve? Uniformly approximate all columns of A? In what norm? I suspect that you won't find anything more efficient than truncated SVD (maybe "more accurate" in some sense but at the cost of "higher complexity"). On a different note: What do you mean by "described by linear components"? What you put the data as columns in a matrix, you assume that they span a linear space in some sense. $\endgroup$
    – Dirk
    Commented Aug 6, 2018 at 10:14

1 Answer 1

Reset to default
2
+25
$\begingroup$

A Non-linear Generalization of Singular Value Decomposition proposes a non-linear extension of the singular value decomposition by appending additional columns to the data matrix which are non-linearly derived from the existing columns.
Section V gives an application to the logistic map, $X_{n+1}=\lambda X_n(1-X_n)$, where $\lambda$ is an unknown parameter that we wish to retrieve from the data. When SVD is applied to a matrix that contains columns with the time series $X_n$ as well as the square $X_n^2$, the appearance of zero singular values indicates a linear relationship between columns, from which an estimate for $\lambda$ is obtained.

Improve this answer
$\endgroup$

You must log in to answer this question.

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