Repository: scikit-learn/scikit-learn
Pull request: [MRG] Add sparse efficiency warning to randomized_svd (fixes randomized_svd is slow for dok_matrix and lil_matrix #11262)
#### Reference Issues/PRs
Fixes #11262

#### What does this implement/fix? Explain your changes.

Adds a `scipy.sparse.SparseEfficiencyWarning` when `randomized_svd` is run on `lil_matrix` or `dok_matrix`.

#### Any other comments?

`coo_matrix` is about 1.5x slower than `csr_matrix`. Maybe it is worth also warning about this, but that's a judgement call. Also worth considering whether it is better to simply coerce the matrix to a better data type, rather than printing a warning.


Problem statement:
randomized_svd is slow for dok_matrix and lil_matrix
#### Description

`sklearn.utils.extmath.randomized_svd` (and its object-oriented interface, `sklearn.decomposition.TruncatedSVD`) is extremely slow for certain types of sparse matrix.

#### Steps/Code to Reproduce

```
>>> import numpy as np
>>> import scipy.sparse as sp
>>> from sklearn.utils.extmath import randomized_svd
>>> import timeit
>>> 
>>> def test(X, seed=42):
>>> 	U, S, VT = randomized_svd(X, 50, random_state=seed)
>>> 
>>> np.random.seed(42)
>>> X = np.random.normal(0,1,[1000,1000]) * np.random.poisson(0.1, [1000,1000])
>>> X = sp.csr_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 381 ms per loop
>>> 
>>> X = sp.csc_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 400 ms per loop
>>> 
>>> X = sp.bsr_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 392 ms per loop
>>> 
>>> X = sp.coo_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 578 ms per loop
>>> 
>>> X = sp.lil_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 1.45 s per loop
>>> 
>>> X = sp.dok_matrix(X)
>>> %timeit -n 50 test(X)
50 loops, best of 3: 22.1 s per loop
```

#### Expected Results

Either all sparse matrices should be processed in roughly the same amount of time, or a warning should be printed.

#### Actual Results

`randomized_svd` silently takes up to 50x longer than necessary.

#### Versions

Windows-10-10.0.17134-SP0
Python 3.6.0 |Anaconda 4.3.1 (64-bit)| (default, Dec 23 2016, 11:57:41) [MSC v.1900 64 bit (AMD64)]
NumPy 1.14.4
SciPy 1.1.0
Scikit-Learn 0.19.1

Also tested on:

Linux-4.16.11-1-ARCH-x86_64-with-arch-Arch-Linux
Python 3.6.5 (default, May 11 2018, 04:00:52)
[GCC 8.1.0]
NumPy 1.14.5
SciPy 1.1.0
Scikit-Learn 0.19.1

Hints from issue discussion:

Commit message: Add sparse efficiency warning to randomized_svd

lil_matrix is 4x slower than csr_matrix, dok_matrix is ~50x slower.

Patch to review:
diff --git a/sklearn/utils/extmath.py b/sklearn/utils/extmath.py
index a619065f26878..a0de2c0def953 100644
--- a/sklearn/utils/extmath.py
+++ b/sklearn/utils/extmath.py
@@ -15,8 +15,7 @@
 import warnings
 
 import numpy as np
-from scipy import linalg
-from scipy.sparse import issparse, csr_matrix
+from scipy import linalg, sparse
 
 from . import check_random_state, deprecated
 from .fixes import np_version
@@ -60,9 +59,9 @@ def row_norms(X, squared=False):
 
     Performs no input validation.
     """
-    if issparse(X):
-        if not isinstance(X, csr_matrix):
-            X = csr_matrix(X)
+    if sparse.issparse(X):
+        if not isinstance(X, sparse.csr_matrix):
+            X = sparse.csr_matrix(X)
         norms = csr_row_norms(X)
     else:
         norms = np.einsum('ij,ij->i', X, X)
@@ -131,7 +130,7 @@ def safe_sparse_dot(a, b, dense_output=False):
     dot_product : array or sparse matrix
         sparse if ``a`` or ``b`` is sparse and ``dense_output=False``.
     """
-    if issparse(a) or issparse(b):
+    if sparse.issparse(a) or sparse.issparse(b):
         ret = a * b
         if dense_output and hasattr(ret, "toarray"):
             ret = ret.toarray()
@@ -322,6 +321,15 @@ def randomized_svd(M, n_components, n_oversamples=10, n_iter='auto',
         # this implementation is a bit faster with smaller shape[1]
         M = M.T
 
+    if isinstance(M, sparse.lil_matrix):
+        warnings.warn("Calculating SVD of a lil_matrix is expensive. "
+                      "csr_matrix is more efficient.",
+                      sparse.SparseEfficiencyWarning)
+    elif isinstance(M, sparse.dok_matrix):
+        warnings.warn("Calculating SVD of a dok_matrix is expensive. "
+                      "csr_matrix is more efficient.",
+                      sparse.SparseEfficiencyWarning)
+
     Q = randomized_range_finder(M, n_random, n_iter,
                                 power_iteration_normalizer, random_state)
 
@@ -620,7 +628,7 @@ def safe_min(X):
     Adapated from http://stackoverflow.com/q/13426580
 
     """
-    if issparse(X):
+    if sparse.issparse(X):
         if len(X.data) == 0:
             return 0
         m = X.data.min()
@@ -633,7 +641,7 @@ def make_nonnegative(X, min_value=0):
     """Ensure `X.min()` >= `min_value`."""
     min_ = safe_min(X)
     if min_ < min_value:
-        if issparse(X):
+        if sparse.issparse(X):
             raise ValueError("Cannot make the data matrix"
                              " nonnegative because it is sparse."
                              " Adding a value to every entry would"


Code review comments:
diff_hunk: @@ -322,6 +321,15 @@ def randomized_svd(M, n_components, n_oversamples=10, n_iter='auto',
         # this implementation is a bit faster with smaller shape[1]
         M = M.T
 
+    if isinstance(M, sparse.lil_matrix):
path: sklearn/utils/extmath.py
text: @user1:
Maybe
```py
if isinstance(M, (sparse.lil_matrix, sparse.dok_matrix)):
    warnings.warn(("Calculating SVD of a %s is expensive. "
                   "csr_matrix is more efficient.")
                   % type(M).__name__))
```