SVD dimensionality reduction for time series of different length

Question

I am using Singular Value Decomposition as a dimensionality reduction technique.

Given N vectors of dimension D, the idea is to represent the features in a transformed space of uncorrelated dimensions, which condenses most of the information of the data in the eigenvectors of this space in a decreasing order of importance.

Now I am trying to apply this procedure to time series data. The problem is that not all the sequences have the same length, thus I cant really build the num-by-dim matrix and apply SVD. My first thought was to pad the matrix with zeros by building a num-by-maxDim matrix and filling the empty spaces with zeros, but I'm not so sure if that is the correct way.

My question is how do you the SVD approach of dimensionality reduction to time series of different length? Alternatively are there any other similar methods of eigenspace representation usually used with time series?

Below is a piece of MATLAB code to illustrate the idea:

X = randn(100,4);                       % data matrix of size N-by-dim

X0 = bsxfun(@minus, X, mean(X));        % standarize
[U S V] = svd(X0,0);                    % SVD
variances = diag(S).^2 / (size(X,1)-1); % variances along eigenvectors

KEEP = 2;                               % number of dimensions to keep
newX = U(:,1:KEEP)*S(1:KEEP,1:KEEP);    % reduced and transformed data

(I am coding mostly in MATLAB, but I'm comfortable enough to read R/Python/.. as well)

Answer 1

There is a reasonably new area of research called Matrix Completion, that probably does what you want. A really nice introduction is given in this lecture by Emmanuel Candes

Answer 2

Just a thought: you might not need the full SVD for your problem. Let M = U S V* be the SVD of your d by n matrix (i.e., the time series are the columns). To achieve the dimension reduction you'll be using the matrices V and S. You can find them by diagonalizing M* M = V (S*S) V*. However, because you are missing some values, you cannot compute M* M. Nevertheless, you can estimate it. Its entries are sums of products of columns of M. When computing any of the SSPs, ignore pairs involving missing values. Rescale each product to account for the missing values: that is, whenever a SSP involves n-k pairs, rescale it by n/(n-k). This procedure is a "reasonable" estimator of M* M and you can proceed from there. If you want to get fancier, maybe multiple imputation techniques or Matrix Completion will help.

(This can be carried out in many statistical packages by computing a pairwise covariance matrix of the transposed dataset and applying PCA or factor analysis to it.)

Answer 3

Filling with zero is bad. Try filling with resampling using observations from the past.

Answer 4

I'm somewhat confused by your example code, as it seems you drop the V variable from the computation of newX. Are you looking to model X as a reduced rank product, or are you interested in a reduced column space of X? in the latter case, I think an EM-PCA approach would work. you can find matlab code under the title Probabilistic PCA with missing values$^\dagger$.

--

$\dagger$ archived version.

Answer 5

You could estimate univariate time series models for the 'short' series and extrapolate them into the future to 'align' all the series.