0
$\begingroup$

I am using Singular Value Decomposition (SVD) applied to Singular Spectrum Analysis (SSA) of a timeseries.

% original time series
x1= rand(1,10000);
N = length(x1);

% windows for trajectory matrix
L = 600;
K=N-L+1; 

% trajectory matrix/matrix of lagged vectors
X = buffer(x1, L, L-1, 'nodelay'); 

% Covariance matrix
A = X * X' / K;

% SVD
[U, S_temp, ~] = svd(A);


% The eigenvalues of A are the squared eigenvalues of X
S = sqrt(S_temp);
d = diag(S);
% Principal components
V = X' * U;
for i = 1 : L
    V(:, i) = V(:, i) / d(i);             
end

EDIT 1:

If I try to reconstruct the original matrix X adding the i-matrices given by d(i)*U(:,i)*V(:,i)' I get exactly the original matrix.

X_rec = zeros(size(X));
for index_col = 1 : L
    disp(index_col)
    X_i = d(index_col)*U(:,index_col)*V(:,index_col)';
    X_rec=X_rec+X_i;
end  

I wanted to know if there is a way to have the singular components V always positive with the compromise of having an error in the recostructed matrix. In this case the reconstructed matrix would be just an approximation of the original.

X is always > 0 in my case (and also the Covariance matrix A)

$\endgroup$
  • 1
    $\begingroup$ What exactly bothers you? That S sometimes has zero values or that U is partly negative? $\endgroup$ – ttnphns Apr 1 '15 at 12:26
  • $\begingroup$ The singular values are in $S$, and they are always non-negative. $\endgroup$ – Tommy L Apr 1 '15 at 12:27
  • $\begingroup$ That some values of V are negative...I edited my question to be more specific $\endgroup$ – gabboshow Apr 1 '15 at 12:27
  • $\begingroup$ possible duplicate of SVD (singular value decomposition) and SSA (singular spectrum analysis) adding constrains on components $\endgroup$ – knedlsepp Apr 1 '15 at 12:45
  • $\begingroup$ According to Frobenius-Perron theorem, if X is positive the fisrt vector in V and in U are complitely positive too. Or, more strictly, either completely positive or completely negative - depending on your svd function realization. $\endgroup$ – ttnphns Apr 1 '15 at 13:59
1
$\begingroup$

Yes, you can add a non-negativity constraint to the right-singular vectors, $V$.

However, you must specify how "far" from 0 the elements can be to be an acceptable solution.

Let your optimisation problem be $$ \text{maximise}\; \frac12\|Xv\|_2^2, $$ $$ \text{subject to}\; \|v\|_2\leq1 \;\text{and}\; v_i > \varepsilon, \forall i. $$ This is a convex optimisation problem with convex constraints. The projection onto the non-negative orthant is $$ \rho_+(x) = \begin{cases} x_i & \text{if}\; x_i > \varepsilon, \forall i\\ \varepsilon & \text{otherwise}. \end{cases} $$ and the projection onto the $\ell_2$ norm ball is $$ \rho_{\ell_2}(x) = \begin{cases} x & \textit{if}\; \|x\|_2<1 \\ \frac{x}{\|x\|_2} & \text{otherwise}. \end{cases} $$

I am not 100 % sure, but I think that the projection onto the intersection of these constraints is: $$ \rho(x) = \rho_{\ell_2}(\rho_+(x)) $$

A trivial algorithm would then be: $$ v^{k+1} = \rho(v^k - t\nabla \frac12\|Xv^k\|_2^2) = \rho(v^k - tX^TXv^k), $$ where $t$ is a step size. This method is called projected gradient descent.

This solution will be the closest approximation (in a squared $\ell_2$ sense) to the SVD, but with a non-negativity constraint on the right-singular vectors.

$\endgroup$
  • $\begingroup$ Hi Thanks for your answer. I am not familiar with optimization problems... could you explain a bit more? is v the same of V? $\endgroup$ – gabboshow Apr 1 '15 at 12:51
  • $\begingroup$ @TommyL: Wiki states: Non-degenerate singular values always have unique left- and right-singular vectors, up to multiplication by a unit-phase factor. So you won't get lucky most of the time. $\endgroup$ – knedlsepp Apr 1 '15 at 12:56
  • $\begingroup$ @gabboshow Yes, $v$ would be a right-singular vector. In order to obtain more than one you would have to either add an orthogonality constraint, or deflate the component from $X$. The simplest is deflation (but it has its own problems). After the first component, let $X := X - Xvv^T$, and run the algorithm again to find the second component. $\endgroup$ – Tommy L Apr 1 '15 at 13:14
  • $\begingroup$ @TommyL What you are suggesting is to iteratively run SVD? run the first time, reconstruct X taking out and saving the first component and running again and again SVD? $\endgroup$ – gabboshow Apr 1 '15 at 13:21
  • $\begingroup$ @knedlsepp I'm not sure what you mean by being lucky. This would not be the singular vectors, but would be the ones maximising the variance, under the constraint of non-negativeness. $\endgroup$ – Tommy L Apr 1 '15 at 13:30

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.