Patent Document ID: 9760537
Application ID: 14525917
Patent Flag: 1

Claim One:
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.