# Singular Value decomposition positive components

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)

• What exactly bothers you? That S sometimes has zero values or that U is partly negative? – ttnphns Apr 1 '15 at 12:26
• The singular values are in $S$, and they are always non-negative. – Tommy L Apr 1 '15 at 12:27
• That some values of V are negative...I edited my question to be more specific – gabboshow Apr 1 '15 at 12:27
• – knedlsepp Apr 1 '15 at 12:45
• 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. – ttnphns Apr 1 '15 at 13:59

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.

• Hi Thanks for your answer. I am not familiar with optimization problems... could you explain a bit more? is v the same of V? – gabboshow Apr 1 '15 at 12:51
• @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. – knedlsepp Apr 1 '15 at 12:56
• @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. – Tommy L Apr 1 '15 at 13:14
• @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? – gabboshow Apr 1 '15 at 13:21
• @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. – Tommy L Apr 1 '15 at 13:30