Weapons-Grade SVD: Fast & Scalable
In this post we’ll show how QLA can accelerate your SVD computations by orders of magnitude.
QLA provides the qsvd function, which computes a fast SVD with very small error tolerance. You can use it wherever you would use Matlab’s built-in svd.
To benchmark performance we measure runtimes on 30 real-world data matrices ranging in size from 43K to 154M entries. See the data table for descriptions and download links.
We compare qsvd against Matlab’s svd with the ‘econ’ option (‘econ’ skips the extra computation of a null space basis). Timings are obtained as follows:
>> load example.mat
>> tic; [u,s,v] = qsvd(mat); toc
Elapsed time is 0.1234 seconds.
>> tic; [u,s,v] = svd(mat, 'econ'); toc
Elapsed time is 6.4312 seconds.
This comparison is conveniently wrapped in compare_qsvd.m, which you can use like this:
>> compare_qsvd(mat)
% compare_qsvd(mat, epsilon) if using a tolerance other than the default 0.01
We ran the comparison at several different qsvd error tolerances (.01, .025, .05) to capture a range of speedups that might be seen in different applications. Results are summarized in this plot:
These results speak for themselves. We see that qsvd accelerates most cases by 10x – 1,000x (note the log scale). A few cases are accelerated only at higher error tolerances, but the majority have significant speedup at all levels.
Why does this matter to you? The SVD is a slow bottleneck inside many applications – optimizations, model fitting, image and signal processing, search engines, data analytics, etc. Drop in QLA’s qsvd, and suddenly you can run 20x faster or handle 100x larger problems. That’s nuclear impact. Why not grab the free version and try it?
| dataset | size |
| galaxy | 40,000 x 3,839 |
| mars | 1,783 x 2,000 |
| declaration | 4,656 x 3,923 |
| bcsstk24 | 3,562 x 3,562 |
| frey | 560 x 1,965 |
| madelon | 4,400 x 500 |
| dor | 800 x 6,063 |
| sonar_scatter | 208 x 208 |
| secom | 1,567 x 590 |
| pumsb | 49,046 x 74 |
| connect | 67,577 x 43 |
| regression | 124,202 x 37 |
| pumsb_star | 49,046 x 63 |
| PIE_32x32 | 11,554 x 1,025 |
| umist | 575 x 10,304 |
| ozone | 2,536 x 73 |
| timit | 138,839 x 40 |
| olivetti | 4,096 x 400 |
| moon | 256 x 384 |
| arrhythmia | 452 x 280 |
| arcene | 800 x 10,000 |
| ailerons | 13,750 x 41 |
| gisette | 12,500 x 5,000 |
| tic | 9,822 x 86 |
| elevators | 16,599 x 19 |
| corel | 61,634 x 16 |
| isolet | 7,797 x 618 |
| usps | 11,000 x 256 |
| poker | 1,025,010 x 11 |
| mnist_reg500 | 70,000 x 784 |