# Speedup of DimensionReduce

I am interested in accelerating DimensionReduce using the "TSNE" method. I have a matrix with a size of 30000 * 10, and I want to reduce to 30000 * 8. But the calculation is very slow, any suggestions on how to speed up the calculation. Currently, I do it in the following manner:

data={{0.0136704, 868., 5., 0., 0., 0., 0.0679724, 1.02337, 5.,
2391.}, {0.0327273, 65., 0., 0., 0., 0., 0.0615385, 1.02337, 5.,
2391.}, {0.0343137, 45., 2., 0., 0., 0., 0.0888889, 0.976633, 3.,
2388.}, {0.0425656, 358., 11., 0.0333333, 0., 0., 0.0642458,
0.976633, 3., 2375.}, {0.0146471, 168., 4., 0.4, 0., 0., 0.0892857,
1.02337, 5., 2378.}, {0.0255665, 362., 6., 0.0833333, 0., 0.,
0.0856354, 1.02337, 5., 2368.}, {0.0215647, 443., 5., 0.0967742, 0.,
0., 0.0857788, 1.02337, 5., 2377.}, {0.0242424, 435., 6.,
0.0294118, 0., 0., 0.110345, 0.976633, 3., 2362.}, {0.0311943, 511.,
22., 0., 0., 0., 0.129159, 1.02337, 5., 2360.}, {0.030086, 171.,
4., 0., 0., 0., 0.122807, 1.02337, 5., 2361.}, {0.0324948, 222.,
10., 0., 0., 0., 0.103604, 0.976633, 3., 2364.}, {0.0232975, 120.,
2., 0., 0., 0., 0.108333, 1.02337, 5., 2380.}, {0.046616, 632., 20.,
0., 0., 0., 0.056962, 1.02337, 5., 2354.}, {0.0187225, 381., 9.,
0., 0., 0., 0.0603675, 1.02337, 5., 2342.}, {0.0234043, 421., 11.,
0.133333, 0., 0., 0.109264, 1.02337, 5., 2384.}, {0.0255072, 375.,
8., 0., 0., 0., 0.0906667, 1.02337, 5., 2359.}, {0.0284264, 240.,
15., 0.125, 0., 0., 0.129167, 1.02337, 5., 2344.}, {0.0246575, 183.,
5., 0., 0., 0., 0.0819672, 1.02337, 5., 2361.}, {0.0155535, 251.,
4., 0., 0., 0., 0.0876494, 0.0233665, 4., 2351.}, {0.0232186, 276.,
10., 0., 0., 0., 0.0688406, 1.02337, 5., 2346.}}

DimensionReduce[data, 8, Method -> {"TSNE", "Perplexity" -> 50},
TargetDevice -> "GPU",
PerformanceGoal -> "Speed"]; // AbsoluteTiming

{0.290914, Null}

DimensionReduce[data, 8, Method -> {"TSNE", "Perplexity" -> 50},
PerformanceGoal -> "Speed"]; // AbsoluteTiming

{0.307318, Null}

• This might be slightly offtopic for this site, but on topic for what you want to do. If you like t-SNE you might want to check out UMAP (github repo, paper). It offers the best of both worlds, global feature preserving methods like singular value decomposition and local feature preserving methods like t-SNE. Also it converges faster than t-SNE. – Thies Heidecke Dec 10 '18 at 16:42

Singular value decomposition may provide a reasonable dimension reduction.

rankreduce[A_?MatrixQ, rank_Integer] :=
Module[{U, Σ, V, r},
r = Min[Max[1, rank], Min[Dimensions[A]]];
{U, Σ, V} = SingularValueDecomposition[A, r];
U.Σ.V\[Transpose]
]


Let's simulate a compressible data set A:

n = 30000;
m = 10;
rank = 8;
SeedRandom[123];
A = Dot[
RandomReal[{-1, 1}, {n, m}],
RandomVariate[CircularRealMatrixDistribution[m]] Exp[-Range[1, m]]
];


And let's see how it works:

A2 = rankreduce[A, rank]; // AbsoluteTiming // First


0.006426

Checking the relative errors:

Norm[A2 - A, ∞]/Norm[A, ∞]
Norm[A2 - A, "Frobenius"]/Norm[A, "Frobenius"]
Norm[A2 - A]/Norm[A]


0.000324675

0.000332843

0.000336114

Of course, the success of the method depends heavily on your data and your actual application. What is performed here is a least-squares fit to an 8-dimension linear subspace, so no sophisticated nonlinear model is developed. But with only 10 data points, it really does not make sense to fit against a complicated nonlinear manifold.

# Edit

The following function is even 4 times faster than rankreduce for this use case. But as it employs the eigenvector decomposition of the matrix Transpose[A].A, this may result in precision issues (Transpose[A].A may have considerably larger condition number than A).

rankreduce2[A_?MatrixQ, rank_Integer] := Module[{λ, U, r},
r = Min[Max[1, rank], Min[Dimensions[A]]];
If[Dimensions[A][[1]] > Dimensions[A][[2]],
{λ, U} = Eigensystem[A\[Transpose].A, r];
(A.U\[Transpose]).U
,
{λ, U} = Eigensystem[A.A\[Transpose], r];
U\[Transpose].(U.A)
]
]

• Actually, SingularValueDecomposition is very fast, if you only need the largest N singular values: e.g. SingularValueDecomposition[A, 10]; // AbsoluteTiming only takes a few milliseconds to calculate the largest 10 singular values – Niki Estner Dec 10 '18 at 8:29
• @NikiEstner Ah, very good point; I forgot about limiting the rank in the first place! – Henrik Schumacher Dec 10 '18 at 8:30