%% Matrix Sketch of Matrix with Slowly Decaying Singular Values
% Use svdsketch with the MaxSubspaceDimension option on a matrix that has slowly decaying singular values. You can use this option to force svdsketch to use a subset of the features of A in the matrix sketch.
%
% Create a 5000-by-5000 matrix with values drawn from the standard normal distribution. View the distribution of matrix singular values.

A = randn(5000);
semilogy(svd(A),'-o')

% Since the singular values in A decay slowly, A has many important features and does not lend itself to low-rank approximations. To form a matrix sketch that reasonably approximates A, most or nearly all of the features need to be preserved.
%
% Use svdsketch on the matrix with a tolerance of 1e-5. Specify four outputs to return the SVD factors as well as the relative approximation error in each iteration.

tol = 1e-5;
[U1,S1,V1,apxError1] = svdsketch(A,tol);
size(S1)

% The size of S indicates that to satisfy the tolerance, svdsketch needs to preserve all of the features of A. For large sparse input matrices, this can present memory issues since the low-rank approximation of A formed by svdsketch is roughly the same size as A and thus might not fit in memory as a dense matrix.
%
% Check the approximation error of the outputs. Since svdsketch preserves everything in A, the computed answer is accurate, but the calculation was just an expensive way to calculate svd(X).

apxError1(end)

%
% Now, do the same calculation but specify MaxSubspaceDimension as 650 to limit the size of the subspace used to sketch A. This is useful to force svdsketch to use only a subset of the features in A to form the matrix sketch, reducing the size of the outputs.

[U2,S2,V2,apxError2] = svdsketch(A,tol,'MaxSubspaceDimension',650);
size(S2)

% The outputs now have a smaller size.
%
% Check the approximation error of the new outputs. The tradeoff for forcing the outputs to be smaller is that many important features of A need to be omitted in the matrix sketch, and the resulting rank 650 approximation of A does not meet the specified tolerance.

apxError2(end)

% Copyright 2020 The MathWorks, Inc.