13
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Good question! I think you can improve the title, there could be something like "missing data" somewhere or "times series of different length". $\endgroup$ – robin girard Aug 4 '10 at 21:19
  • 1
    $\begingroup$ I wouldn't call it "missing data", perhaps "SVD dimensionality reduction for time series of different length"? $\endgroup$ – Amro Aug 4 '10 at 21:45
  • 1
    $\begingroup$ I like the title you propose ! $\endgroup$ – robin girard Aug 5 '10 at 5:27
  • 1
    $\begingroup$ it would also help to know why the series are of different lengths. For example, if they represent the trajectory of a pencil during a handwriting task, say the X displacement while writing out a digit, then you might want to align the time series so that they are the same length. It is also important to know what type of variation you are interested in retaining, and what you are not. $\endgroup$ – vqv Dec 19 '10 at 22:02
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 for the web site VideoLecture, I did not know, did you mention it in the question about video lectures ? $\endgroup$ – robin girard Aug 9 '10 at 12:34
  • $\begingroup$ I've only being reading about this stuff recently. I really like Candes and Tao's recent paper on the topic arxiv.org/abs/0903.1476 $\endgroup$ – Robby McKilliam Aug 9 '10 at 12:55
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 replication/resampling are definitely better than zero-padding.. still I'll wait and see if there are any other ideas out there :) $\endgroup$ – Amro Aug 4 '10 at 21:43
2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ this procedure results in an estimate of $M^T M$ that may not be positive semidefinite, which would be bad. $\endgroup$ – shabbychef Aug 18 '10 at 0:40
  • $\begingroup$ That's a good point, but the result might not be so bad. What one hopes is that the estimate of M*M is close enough to the true value that the perturbation of eigenvalues is reasonably small. Thus, by projecting to the eigenspace corresponding to the largest eigenvalues, you achieve only a slight perturbation of the correct solution, still achieving the sought-after dimension reduction. Perhaps the biggest problem may be algorithmic: since you can no longer assume semidefiniteness, you might need to use a more general-purpose algorithm to find the eigensystem. $\endgroup$ – whuber Aug 18 '10 at 14:09
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ extrapolation would include smoothness in the filled part that does not exists in the existing part. You have to add randomness... hence resampling (and resmapling on the extrapolation seems to be a good idea) $\endgroup$ – robin girard Aug 6 '10 at 14:28
  • $\begingroup$ Extrapolating the model would require sampling the error term which would induce the desired randomness. $\endgroup$ – user28 Aug 6 '10 at 14:53
  • $\begingroup$ IMO both suggestions boil down to predicting future values from existing ones (AR/ARMA models perhaps?). I guess I'm still hoping for a solution that doesn't involve sampling values (thus the possibility of introducing error).. Besides estimating such models is in itself a form of dimensionality reduction :) $\endgroup$ – Amro Aug 6 '10 at 22:19
1
$\begingroup$

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.

hth,

$\endgroup$
  • $\begingroup$ I am not trying to compute a reduced-rank approximation of X, rather a transformed X. You see my goal is not to filter noisy sequences, but to find a representation with a reduced dimensionality (to be used for classification/clustering of time series)... Could you elaborate a bit on the EM-PCA approach? $\endgroup$ – Amro Aug 9 '10 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.