Finding a CUR decomposition

1. A computer-implemented method for reducing storage space occupied by a matrix A, the computer-implemented method comprising:

constructing, by a first hardware circuit, a matrix C based on the matrix A, wherein the constructing the matrix C based on the matrix A comprises:

computing Z 1 as the top k singular vectors of A, wherein a scalar k is a target rank of a matrix U and is selected to be less than the rank of the matrix A, wherein A k is a rank-k approximation of the matrix A, wherein a scalar ε is between 0 and 1 and represents a selected accuracy parameter, and wherein ∥A−AZ 1 Z 1 T ∥ F 2 ≦(1+ε)∥A−A k ∥ F 2 ;

sampling O(k log k) columns from the transpose of Z 1 , wherein the sampling uses leverage scores;

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns, wherein ∥A C 1 C 1 † ∥ F 2 ≦O(1)∥A AZ 1 Z 1 T ∥ F 2 ; and

adaptively sampling c 2 =O(k/ε) columns of A, wherein



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

,

wherein D is selected to be a rank-k matrix;

constructing, by a second hardware circuit distinct from the first hardware circuit, a matrix R based on the matrix A and the matrix C;

constructing, by a third hardware circuit distinct from the first hardware circuit and the second hardware circuit, the matrix U based on the matrices A, C, and R;

wherein the matrices C, U, and R comprise a CUR decomposition of the matrix A;

reducing storage space occupied by the matrix A by replacing the matrix A with the matrices C, U, and R.

2. The method of claim 1 , wherein the constructing the matrix R based on the matrix A and the matrix C comprises:



Λ

-

Λ

⁢

⁢

Z

1

⁢

Z

1

T



F

2

≤

(

1

+

ɛ

)

⁢



Λ

-

Λ

R



F

2

⁢



A

-

C

1

⁢

C

1

†



F

2

≤

O

⁡

(

1

)

⁢



A

-

AZ

1

⁢

Z

1

T



F

2

⁢



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

;

and finding Z 2 in the span of the matrix C, wherein ∥Λ−ΛZ 2 Z 2 T ∥ F 2 ≦(1+ε)∥Λ−Λ k ∥ F 2 ;

sampling O(k log k) rows of Z 2 , wherein the sampling uses leverage scores;

down-sampling the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling, wherein ∥A R 1 R 1 † ∥ F 2 ≦O(1)∥A AZ 2 Z 2 T A∥ F 2 ; and

adaptively sampling r 2 =O(k/ε) rows of A, wherein



A

-

Z

2

⁢

Z

2

T

⁢

AR

†

⁢

R



F

2

≤



A

-

Z

2

⁢

Z

2

T

⁢

A



F

2

+

rank

(

Z

1

⁢

Z

2

T

⁢

A

r

2

)

⁢



A

-

AR

1

⁢

R

1

†



F

2

.

3. The method of claim 2 , further comprising projecting one or more columns of the matrix A*W onto the matrix C, wherein the matrix W is a random subspace embedding.

4. The method of claim 2 , wherein:

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns using BSS sampling uses an input-sparsity-time BSS sampling algorithm;

adaptively sampling c 2 =O(k/ε) columns of A occurs in input-sparsity time;

down-sampling the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling uses the input-sparsity-time BSS sampling algorithm;

adaptively sampling r 2 =O(k/ε) rows of A occurs in input-sparsity time; and

constructing the matrix U based on the matrices A, C, and R is performed in input -sparsity time.

5. The method of claim 4 , wherein the construction of the matrices C, U, and R occurs in input-sparsity time.

6. The method of claim 2 , wherein:

adaptively sampling c 2 =O(k/ε) columns of A comprises derandomization; and

adaptively sampling r 2 =O(k/ε) rows of A comprises derandomization.

7. The method of claim 6 , wherein the construction of the matrices C, U, and R comprises a deterministic CUR decomposition.

8. A system for reducing storage space occupied by a matrix A, the system comprising:

a memory; and

one or more processors, communicatively coupled to the memory, the one or more processors configured to:

construct, by a first hardware circuit, a matrix C based on the matrix A, wherein the constructing the matrix C based on the matrix A comprises:

computing Z 1 as the top k singular vectors of A, wherein a scalar k is a target rank of a matrix U and is selected to be less than the rank of the matrix A, wherein A k is a rank-k approximation of the matrix A, wherein a scalar ε is between 0 and 1 and represents a selected accuracy parameter, and wherein ∥A−AZ 1 Z 1 T ∥ F 2 ≦(1+ε)∥A−A k ∥ F 2 ;

sampling O(k log k) columns from the transpose of Z 1 , wherein the sampling uses leverage scores;

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns, wherein ∥A C 1 C 1 † ∥ F 2 ≦O(1)∥A AZ 1 Z 1 T ∥ F 2 ; and

adaptively sampling c 2 =O(k/ε) columns of A, wherein



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

,

 wherein D is selected to be a rank-k matrix;

construct, by a second hardware circuit distinct from the first hardware circuit, a matrix R based on the matrix A and the matrix C; and

construct, by a third hardware circuit distinct from the first hardware circuit and the second hardware circuit, the matrix U based on the matrices A, C, and R;

wherein the matrices C, U, and R comprise a CUR decomposition of the matrix A; and

reduce storage space occupied by the matrix A by replacing the matrix A with the matrices C, U, and R.

9. The system of claim 8 , wherein to construct the matrix R based on the matrix A and the matrix C, the one or more processors are further configured to:



Λ

-

Λ

⁢

⁢

Z

1

⁢

Z

1

T



F

2

≤

(

1

+

c

)

⁢



Λ

-

Λ

k



F

2

⁢



A

-

C

1

⁢

C

1

l



F

2

≤

O

⁡

(

1

)

⁢



A

-

A

⁢

⁢

Z

1

⁢

Z

1

T



F

2

⁢



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

;

and find Z 2 in the span of the matrix C, wherein ∥Λ−ΛZ 2 Z 2 T ∥ F 2 ≦(1+ε)∥Λ−Λ k ∥ F 2 ;

sample O(k log k) rows of Z 2 , wherein the sampling uses leverage scores;

down-sample the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling, wherein ∥A−R 1 R 1 l ∥ F 2 ≦O(1)∥A−AZ 2 Z 2 T A∥ F 2 ; and

adaptively sample r 2 =O(k/ε) rows of A, wherein



A

-

Z

2

⁢

Z

2

T

⁢

AR

†

⁢

R



F

2

≤



A

-

Z

2

⁢

Z

2

T

⁢

A



F

2

+

rank

(

Z

1

⁢

Z

2

T

⁢

A

r

2

)

⁢



A

-

AR

1

⁢

R

1

†



F

2

.

10. The system of claim 9 , wherein the one or more processors are further configured to project one or more columns of the matrix A*W onto the matrix C, and wherein the matrix W is a random subspace embedding.

11. The system of claim 9 , wherein:

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns using BSS sampling uses an input-sparsity-time BSS sampling algorithm;

adaptively sampling c 2 =O(k/ε) columns of A occurs in input-sparsity time;

down-sampling the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling uses the input-sparsity-time BSS sampling algorithm;

adaptively sampling r 2 =O(k/ε) rows of A occurs in input-sparsity time; and

constructing the matrix U based on the matrices A, C, and R is performed in input -sparsity time.

12. The system of claim 11 , wherein the construction of the matrices C, U, and R occurs in input-sparsity time.

13. The system of claim 9 , wherein:

adaptively sampling c 2 =O(k/ε) columns of A comprises derandomization; and

adaptively sampling r 2 =O(k/ε) rows of A comprises derandomization.

14. The system of claim 13 , wherein the construction of the matrices C, U, and R comprises a deterministic CUR decomposition.

15. A computer program product for reducing storage space occupied by a matrix A, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more processors to cause the one or more processors to perform a method comprising:

constructing, by a first hardware circuit, a matrix C based on the matrix A, wherein the constructing the matrix C based on the matrix A comprises:

computing Z 1 as the top k singular vectors of A, wherein a scalar k is a target rank of a matrix U and is selected to be less than the rank of the matrix A, wherein A k is a rank-k approximation of the matrix A, wherein a scalar ε is between 0 and 1 and represents a selected accuracy parameter, and wherein ∥A−AZ 1 Z 1 T ∥ F 2 ≦(1+ε)∥A−A k ∥ F 2 ;

sampling O(k log k) columns from the transpose of Z 1 , wherein the sampling uses leverage scores;

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns, wherein ∥A−C 1 C 1 † ∥ F 2 ≦O(1)∥A−AZ 1 Z 1 T ∥ F 2 ; and

adaptively sampling c 2 =O(k/ε) columns of A, wherein



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

,

wherein D is selected to be a rank-k matrix;

constructing, by a second hardware circuit distinct from the first hardware circuit, a matrix R based on the matrix A and the matrix C; and

constructing, by a third hardware circuit distinct from the first hardware circuit and the second hardware circuit, the matrix U based on the matrices A, C, and R;

wherein the matrices C, U, and R comprise a CUR decomposition of the matrix A; and

reducing storage space occupied by the matrix A by replacing the matrix A with the matrices C, U, and R.

16. The computer program product of claim 15 , wherein the constructing the matrix R based on the matrix A and the matrix C comprises:



Λ

-

Λ

⁢

⁢

Z

1

⁢

Z

1

T



F

2

≤

(

1

+

ɛ

)

⁢



Λ

-

Λ

k



F

2

⁢



A

⁢

⁢

C

1

⁢

C

1

†



F

2

≤

O

⁡

(

1

)

⁢



A

⁢

⁢

A

⁢

⁢

Z

1

⁢

Z

1

T



F

2

⁢



A

-

C

·

D



F

2

≤



A

-

A

k



F

2

+

(

k

c

2

)

⁢



A

-

C

1

⁢

C

1

†

⁢

A



F

2

;

and finding Z 2 in the span of the matrix C, wherein ∥A−A% 2 % 2 T ∥ F 2 <(1+ε)∥A−A k ∥ F 2 ;

sampling O(k log k) rows of Z 2 , wherein the sampling uses leverage scores;

down-sampling the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling, wherein ∥A R 1 R 1 † ∥ F 2 ≦O(1)∥A AZ 2 Z 2 T A∥ F 2 ; and

adaptively sampling r 2 =O(k/ε) rows of A, wherein



A

-

Z

2

⁢

Z

2

T

⁢

AR

†

⁢

R



F

2

≤



A

-

Z

2

⁢

Z

2

T

⁢

A



F

2

+

rank

(

Z

1

⁢

Z

2

T

⁢

A

r

2

)

⁢



A

-

AR

1

⁢

R

1

†



F

2

.

17. The computer program product of claim 16 , wherein:

down-sampling the sampled columns to C 1 comprising c 1 =O(k) columns using BSS sampling uses an input-sparsity-time BSS sampling algorithm;

adaptively sampling c 2 =O(k/ε) columns of A occurs in input-sparsity time;

down-sampling the sampled rows to R 1 comprising r 1 =O(k) columns using BSS sampling uses the input-sparsity-time BSS sampling algorithm;

adaptively sampling r 2 =O(k/ε) rows of A occurs in input-sparsity time; and

constructing the matrix U based on the matrices A, C, and R is performed in input- sparsity time.

18. The computer program product of claim 17 , wherein the construction of the matrices C, U, and R occurs in input-sparsity time.

19. The computer program product of claim 16 , wherein:

adaptively sampling c 2 =O(k/ε) columns of A comprises derandomization; and

adaptively sampling r 2 =O(k/ε) rows of A comprises derandomization.

20. The computer program product of claim 19 , wherein the construction of the matrices C, U, and R comprises a deterministic CUR decomposition.