/* ----------------------------------------------------------------------- *//** * * @file svd.sql_in * * @brief Singular Value Decomposition * * @sa For a brief introduction to singular value decomposition, see the module * description \ref grp_svd. * *//* ----------------------------------------------------------------------- */ m4_include(`SQLCommon.m4') /** @addtogroup grp_svd
Contents
@brief Performs factorization of dense and sparse matrices. In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics. Let \f$A\f$ be a \f$mxn\f$ matrix, where \f$m \ge n\f$. Then \f$A\f$ can be decomposed as follows: \f[ A = U \Sigma V^T, \f] where \f$U\f$ is a \f$m \times n\f$ orthonormal matrix, \f$\Sigma\f$ is a \f$n \times n\f$ diagonal matrix, and \f$V\f$ is an \f$n \times n\f$ orthonormal matrix. The diagonal elements of \f$\Sigma\f$ are called the singular values. @anchor syntax @par SVD Functions SVD factorizations are provided for dense and sparse matrices. In addition, a native implementation is provided for very sparse matrices for improved performance. SVD Function for Dense Matrices 
svd( source_table,
     output_table_prefix,
     row_id,
     k,
     n_iterations,
     result_summary_table
);
\b Arguments
source_table
TEXT. Source table name (dense matrix). The table contains a \c row_id column that identifies each row, with numbering starting from 1. The other columns contain the data for the matrix. There are two possible dense formats as illustrated by the 2x2 matrix example below. You can use either of these dense formats: -# 
            row_id     col1     col2
row1         1           1         0
row2         2           0         1
-# 
        row_id     row_vec
row1        1       {1, 0}
row2        2       {0, 1}
output_table_prefix
TEXT. Prefix for output tables. See Output Tables below for a description of the convention used.
row_id
TEXT. ID for each row.
k
INTEGER. Number of singular values to compute.
n_iterations (optional).
INTEGER. Number of iterations to run. @note The number of iterations must be in the range [k, column dimension], where k is number of singular values.
result_summary_table (optional)
TEXT. The name of the table to store the result summary.
SVD Function for Sparse Matrices Use this function for matrices that are represented in the sparse-matrix format (example below). Note that the input matrix is converted to a dense matrix before the SVD operation, for efficient computation reasons. 
svd_sparse( source_table,
            output_table_prefix,
            row_id,
            col_id,
            value,
            row_dim,
            col_dim,
            k,
            n_iterations,
            result_summary_table
          );
\b Arguments
source_table
TEXT. Source table name (sparse matrix). A sparse matrix is represented using the row and column indices for each non-zero entry of the matrix. This representation is useful for matrices containing multiple zero elements. Below is an example of a sparse 4x7 matrix with just 6 out of 28 entries being non-zero. The dimensionality of the matrix is inferred using the max value in row and col columns. Note the last entry is included (even though it is 0) to provide the dimensionality of the matrix, indicating that the 4th row and 7th column contain all zeros. 
 row_id | col_id | value
--------+--------+-------
      1 |      1 |     9
      1 |      5 |     6
      1 |      6 |     6
      2 |      1 |     8
      3 |      1 |     3
      3 |      2 |     9
      4 |      7 |     0
(6 rows)
output_table_prefix
TEXT. Prefix for output tables. See Output Tables below for a description of the convention used.
row_id
TEXT. Name of the column containing the row index for each entry in sparse matrix.
col_id
TEXT. Name of the column containing the column index for each entry in sparse matrix.
value
TEXT. Name of column containing the non-zero values of the sparse matrix.
row_dim
INTEGER. Number of rows in matrix.
col_dim
INTEGER. Number of columns in matrix.
k
INTEGER. Number of singular values to compute.
n_iterations (optional)
INTEGER. Number of iterations to run. @note The number of iterations must be in the range [k, column dimension], where k is number of singular values.
result_summary_table (optional)
TEXT. The name of the table to store the result summary.
Native Implementation for Sparse Matrices Use this function for matrices that are represented in the sparse-matrix format (see sparse matrix example above). This function uses the native sparse representation while computing the SVD. @note Note that this function should be favored if the matrix is highly sparse, since it computes very sparse matrices efficiently. 
svd_sparse_native( source_table,
                   output_table_prefix,
                   row_id,
                   col_id,
                   value,
                   row_dim,
                   col_dim,
                   k,
                   n_iterations,
                   result_summary_table
                 );
\b Arguments
source_table
TEXT. Source table name (sparse matrix - see example above).
output_table_prefix
TEXT. Prefix for output tables. See Output Tables below for a description of the convention used.
row_id
TEXT. ID for each row.
col_id
TEXT. ID for each column.
value
TEXT. Non-zero values of the sparse matrix.
row_dim
INTEGER. Row dimension of sparse matrix.
col_dim
INTEGER. Col dimension of sparse matrix.
k
INTEGER. Number of singular values to compute.
n_iterations (optional)
INTEGER. Number of iterations to run. @note The number of iterations must be in the range [k, column dimension], where k is number of singular values.
result_summary_table (optional)
TEXT. Table name to store result summary.
@anchor output @par Output Tables Output for eigenvectors/values is in the following three tables: - Left singular matrix: Table is named \_u (e.g. ‘netflix_u’) - Right singular matrix: Table is named \_v (e.g. ‘netflix_v’) - Singular values: Table is named \_s (e.g. ‘netflix_s’) The left and right singular vector tables are of the format:
row_id INTEGER. The ID corresponding to each eigenvalue (in decreasing order).
row_vec FLOAT8[]. Singular vector elements for this row_id. Each array is of size k.
The singular values table is in sparse table format, since only the diagonal elements of the matrix are non-zero:
row_id INTEGER. \e i for \e ith eigenvalue.
col_id INTEGER. \e i for \e ith eigenvalue (same as row_id).
value FLOAT8. Eigenvalue.
All \c row_id and \c col_id in the above tables start from 1. The result summary table has the following columns:
rows_used INTEGER. Number of rows used for SVD calculation.
exec_time FLOAT8. Total time for executing SVD.
iter INTEGER. Total number of iterations run.
recon_error FLOAT8. Total quality score (i.e. approximation quality) for this set of orthonormal basis.
relative_recon_error FLOAT8. Relative quality score.
In the result summary table, the reconstruction error is computed as \f$ \sqrt{mean((X - USV^T)_{ij}^2)} \f$, where the average is over all elements of the matrices. The relative reconstruction error is then computed as ratio of the reconstruction error and \f$ \sqrt{mean(X_{ij}^2)} \f$. @anchor examples @examp -# View online help for the SVD function. 
SELECT madlib.svd();
-# Create an input dataset (dense matrix). 
DROP TABLE IF EXISTS mat, mat_sparse, svd_summary_table, svd_u, svd_v, svd_s;
CREATE TABLE mat (
    row_id integer,
    row_vec double precision[]
);
INSERT INTO mat VALUES
(1,'{396,840,353,446,318,886,15,584,159,383}'),
(2,'{691,58,899,163,159,533,604,582,269,390}'),
(3,'{293,742,298,75,404,857,941,662,846,2}'),
(4,'{462,532,787,265,982,306,600,608,212,885}'),
(5,'{304,151,337,387,643,753,603,531,459,652}'),
(6,'{327,946,368,943,7,516,272,24,591,204}'),
(7,'{877,59,260,302,891,498,710,286,864,675}'),
(8,'{458,959,774,376,228,354,300,669,718,565}'),
(9,'{824,390,818,844,180,943,424,520,65,913}'),
(10,'{882,761,398,688,761,405,125,484,222,873}'),
(11,'{528,1,860,18,814,242,314,965,935,809}'),
(12,'{492,220,576,289,321,261,173,1,44,241}'),
(13,'{415,701,221,503,67,393,479,218,219,916}'),
(14,'{350,192,211,633,53,783,30,444,176,932}'),
(15,'{909,472,871,695,930,455,398,893,693,838}'),
(16,'{739,651,678,577,273,935,661,47,373,618}');
-# Run SVD function for a dense matrix. 
SELECT madlib.svd( 'mat',       -- Input table
                   'svd',       -- Output table prefix
                   'row_id',    -- Column name with row index
                   10,          -- Number of singular values to compute
                   NULL,        -- Use default number of iterations
                   'svd_summary_table'  -- Result summary table
                 );
-# Print out the singular values and the summary table. For the singular values: 
SELECT * FROM svd_s ORDER BY row_id;
Result: 
 row_id | col_id |      value
 --------+--------+------------------
      1 |      1 | 6475.67225281804
      2 |      2 | 1875.18065580415
      3 |      3 | 1483.25228429636
      4 |      4 | 1159.72262897427
      5 |      5 | 1033.86092570574
      6 |      6 | 948.437358703966
      7 |      7 | 795.379572772455
      8 |      8 | 709.086240684469
      9 |      9 | 462.473775959371
     10 |     10 | 365.875217945698
     10 |     10 |
(11 rows)
For the summary table: 
SELECT * FROM svd_summary_table;
Result: 
 rows_used | exec_time (ms) | iter |    recon_error    | relative_recon_error
 -----------+----------------+------+-------------------+----------------------
        16 |        1332.47 |   10 | 4.36920148766e-13 |    7.63134130332e-16
(1 row)
-# Create a sparse matrix by running the \ref matrix_sparsify() utility function on the dense matrix. 
SELECT madlib.matrix_sparsify('mat',
                              'row=row_id, val=row_vec',
                              'mat_sparse',
                              'row=row_id, col=col_id, val=value');
-# Run the SVD function for a sparse matrix. 
SELECT madlib.svd_sparse( 'mat_sparse',   -- Input table
                          'svd',          -- Output table prefix
                          'row_id',       -- Column name with row index
                          'col_id',       -- Column name with column index
                          'value',        -- Matrix cell value
                          16,             -- Number of rows in matrix
                          10,             -- Number of columns in matrix
                          10              -- Number of singular values to compute
                          );
-# Run the SVD function for a very sparse matrix. 
SELECT madlib.svd_sparse_native ( 'mat_sparse',   -- Input table
                          'svd',          -- Output table prefix
                          'row_id',       -- Column name with row index
                          'col_id',       -- Column name with column index
                          'value',        -- Matrix cell value
                          16,             -- Number of rows in matrix
                          10,             -- Number of columns in matrix
                          10              -- Number of singular values to compute
                          );
@anchor background @par Technical Background In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics. Let \f$A\f$ be a \f$m \times n\f$ matrix, where \f$m \ge n\f$. Then \f$A\f$ can be decomposed as follows: \f[ A = U \Sigma V^T, \f] where \f$U\f$ is a \f$m \times n\f$ orthonormal matrix, \f$\Sigma\f$ is a \f$n \times n\f$ diagonal matrix, and \f$V\f$ is an \f$n \times n\f$ orthonormal matrix. The diagonal elements of \f$\Sigma\f$ are called the singular values. It is possible to formulate the problem of computing the singular triplets (\f$\sigma_i, u_i, v_i\f$) of \f$A\f$ as an eigenvalue problem involving a Hermitian matrix related to \f$A\f$. There are two possible ways of achieving this: - With the cross product matrix, \f$A^TA\f$ and \f$AA^T\f$ - With the cyclic matrix \f[ H(A) = \begin{bmatrix} 0 & A\\ A^* & 0 \end{bmatrix} \f] The singular values are the nonnegative square roots of the eigenvalues of the cross product matrix. This approach may imply a severe loss of accuracy in the smallest singular values. The cyclic matrix approach is an alternative that avoids this problem, but at the expense of significantly increasing the cost of the computation. Computing the cross product matrix explicitly is not recommended, especially in the case of sparse A. Bidiagonalization was proposed by Golub and Kahan [citation?] as a way of tridiagonalizing the cross product matrix without forming it explicitly. Consider the following decomposition \f[ A = P B Q^T, \f] where \f$P\f$ and \f$Q\f$ are unitary matrices and \f$B\f$ is an \f$m \times n\f$ upper bidiagonal matrix. Then the tridiagonal matrix \f$B*B\f$ is unitarily similar to \f$A*A\f$. Additionally, specific methods exist that compute the singular values of \f$B\f$ without forming \f$B*B\f$. Therefore, after computing the SVD of B, \f[ B = X\Sigma Y^T, \f] it only remains to compute the SVD of the original matrix with \f$U = PX\f$ and \f$V = QY\f$. */ -- ----------------------------------------------------------------------- -- Main function for SVD (Dense format) -- ----------------------------------------------------------------------- /* @brief Compute an singular value decomposition for a dense matrix stored in a database table */ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd( source_table TEXT, -- Source table name (dense array-format matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- ID for each row k INTEGER, -- Number of singular vectors to compute n_iterations INTEGER, -- Iteration number of Lanczos result_summary_table TEXT -- Table name to store result summary ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.svd(schema_madlib, source_table, output_table_prefix, row_id, k, n_iterations, result_summary_table) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); -- ----------------------------------------------------------------------- -- Main function for SVD (Block format) -- Each row in the input table is a triple: -- ----------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_block( source_table TEXT, -- Source table name (dense block-format matrix) output_table_prefix TEXT, -- Prefix for output tables k INTEGER, -- Number of singular vectors to compute n_iterations INTEGER, -- Iteration number of Lanczos result_summary_table TEXT -- Table name to store result summary ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.svd_block(schema_madlib, source_table, output_table_prefix, k, n_iterations, result_summary_table) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_block( source_table TEXT, -- Source table name (dense block-format matrix) output_table_prefix TEXT, -- Prefix for output tables k INTEGER, -- Number of singular vectors to compute n_iterations INTEGER -- Iteration number of Lanczos ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_block($1, $2, $3, $4, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_block( source_table TEXT, -- Source table name (dense block-format matrix) output_table_prefix TEXT, -- Prefix for output tables k INTEGER -- Number of singular vectors to compute ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_block($1, $2, $3, NULL, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); -- ----------------------------------------------------------------------- -- Main Function for SVD (sparse format) -- ----------------------------------------------------------------------- /* @brief Compute an singular value decomposition for a sparse matrix stored in a database table ('input_table', 'output_table_prefix', ’row_id', ’col_id', 'value', row_dim, col_dim, k, 'result_summary_table') */ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER, -- Number of singular vectors with dominant singular values, sorted decreasingly n_iterations INTEGER, -- Iteration number of Lanczos result_summary_table TEXT -- Table name to store result summary ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.svd_sparse(schema_madlib, source_table, output_table_prefix, row_id, col_id, val_id, row_dim, col_dim, k, n_iterations, result_summary_table) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse_native( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER, -- Number of singular vectors with dominant singular values, -- sorted decreasingly n_iterations INTEGER, -- Iteration number of Lanczos result_summary_table TEXT -- Table name to store result summary ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.svd_sparse_native(schema_madlib, source_table, output_table_prefix, row_id, col_id, val_id, row_dim, col_dim, k, n_iterations, result_summary_table) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); -- ----------------------------------------------------------------------- -- Overloaded functions for optional parameters -- ----------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- ID for each row k INTEGER -- Number of singular vectors to compute ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd($1, $2, $3, $4, NULL, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER -- Number of singular vectors with dominant singular values, sorted decreasingly ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_sparse($1, $2, $3, $4, $5, $6, $7, $8, NULL, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- ID for each row k INTEGER, -- Number of singular vectors to compute n_iterations INTEGER -- Iteration number of Lanczos ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd($1, $2, $3, $4, $5, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER, -- Number of singular vectors with dominant singular values, sorted decreasingly n_iterations INTEGER -- Iteration number of Lanczos ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_sparse($1, $2, $3, $4, $5, $6, $7, $8, $9, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse_native( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER -- Number of singular vectors with dominant singular -- values, sorted decreasingly ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_sparse_native($1, $2, $3, $4, $5, $6, $7, $8, NULL, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd_sparse_native( source_table TEXT, -- Source table name (dense matrix) output_table_prefix TEXT, -- Prefix for output tables row_id TEXT, -- Name of ‘row_id’ column in sparse matrix representation col_id TEXT, -- Name of 'col_id' column in sparse matrix representation val_id TEXT, -- Name of 'val_id' column in sparse matrix representation row_dim INTEGER, -- row dimension of sparse matrix col_dim INTEGER, -- col dimension of sparse matrix k INTEGER, -- Number of singular vectors with dominant singular values, sorted decreasingly n_iterations INTEGER -- Iteration number of Lanczos ) RETURNS VOID AS $$ SELECT MADLIB_SCHEMA.svd_sparse_native($1, $2, $3, $4, $5, $6, $7, $8, $9, NULL) $$ LANGUAGE SQL m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `');; --------------------------------------------------------------------- ------------------------Internal Functions--------------------------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_unit_vector ( dim INT -- Dimension of the vector ) -- RETURNS MADLIB_SCHEMA.__svd_unit_vector_result RETURNS DOUBLE PRECISION[] AS 'MODULE_PATHNAME', 'svd_unit_vector' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); DROP TYPE IF EXISTS MADLIB_SCHEMA.__svd_lanczos_result CASCADE; CREATE TYPE MADLIB_SCHEMA.__svd_lanczos_result AS ( scalar FLOAT8, -- alpha/beta vec FLOAT8[] -- pvec/qvec ); --------------------------------------------------------------------- -------Common Aggregator for Computing Lanzcos P/Q Vectors----------- --------------------------------------------------------------------- --------------------------------------------------------------------- ---------------------For Array-Format Matrix------------------------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_sfunc ( state FLOAT8[], -- A * q_j OR A_Trans * p_(j-1) row_id INT, -- Matrix row id row_array FLOAT8[], -- Matrix row array vector FLOAT8[], -- q_j OR p_(j-1) dimension INT -- row_dim OR col_dim ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_lanczos_sfunc' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); --------------------------------------------------------------------- ---------------------For Block-Format Matrix------------------------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_block_lanczos_sfunc ( state FLOAT8[], -- A * q_j OR A_Trans * p_(j-1) row_id INT4, -- Matrix block row id col_id INT4, -- Matrix block col id block FLOAT8[], -- Matrix block vector FLOAT8[], -- q_j OR p_(j-1) dimension INT4 -- row_dim OR col_dim ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_block_lanczos_sfunc' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); --------------------------------------------------------------------- ---------------------For Sparse-Format Matrix------------------------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_sparse_lanczos_sfunc ( state FLOAT8[], -- A * q_j OR A_Trans * p_(j-1) row_id INT4, -- row id col_id INT4, -- col id val FLOAT8, -- value vector FLOAT8[], -- q_j OR p_(j-1) dimension INT4 -- row_dim OR col_dim ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_sparse_lanczos_sfunc' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_prefunc ( state1 FLOAT8[], state2 FLOAT8[] ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_lanczos_prefunc' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); --------------------------------------------------------------------- ---------------------For Array-Format Matrix------------------------- --------------------------------------------------------------------- DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.__svd_lanczos_agg ( INT, -- Matrix row id FLOAT8[], -- Matrix row array FLOAT8[], -- q_j OR p_(j-1) INT -- row_dim OR col_dim ); CREATE AGGREGATE MADLIB_SCHEMA.__svd_lanczos_agg ( INT, -- Matrix row id FLOAT8[], -- Matrix row array FLOAT8[], -- q_j OR p_(j-1) INT -- row_dim OR col_dim ) ( stype = FLOAT8[], sfunc = MADLIB_SCHEMA.__svd_lanczos_sfunc m4_ifdef( `__POSTGRESQL__', `', `, prefunc = MADLIB_SCHEMA.__svd_lanczos_prefunc' ) ); --------------------------------------------------------------------- ---------------------For Block-Format Matrix------------------------- --------------------------------------------------------------------- DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.__svd_block_lanczos_agg ( INT4, -- Matrix block row id INT4, -- Matrix block col id FLOAT8[], -- Matrix block FLOAT8[], -- q_j OR p_(j-1) INT4 -- row_dim OR col_dim ); CREATE AGGREGATE MADLIB_SCHEMA.__svd_block_lanczos_agg ( INT, -- Matrix block row id INT4, -- Matrix block col id FLOAT8[], -- Matrix row array FLOAT8[], -- q_j OR p_(j-1) INT -- row_dim OR col_dim ) ( stype = FLOAT8[], --Note that only the sfunc is different sfunc = MADLIB_SCHEMA.__svd_block_lanczos_sfunc m4_ifdef( `__POSTGRESQL__', `', `, prefunc = MADLIB_SCHEMA.__svd_lanczos_prefunc' ) ); --------------------------------------------------------------------- ---------------------For Sparse-Format Matrix------------------------- --------------------------------------------------------------------- DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.__svd_sparse_lanczos_agg ( INT4, -- Row ID INT4, -- Column ID FLOAT8, -- Value FLOAT8[], -- q_j OR p_(j-1) INT4 -- row_dim OR col_dim ); CREATE AGGREGATE MADLIB_SCHEMA.__svd_sparse_lanczos_agg ( INT4, -- Row ID INT4, -- Column ID FLOAT8, -- Value FLOAT8[], -- q_j OR p_(j-1) INT4 -- row_dim OR col_dim ) ( stype = FLOAT8[], --Note that only the sfunc is different sfunc = MADLIB_SCHEMA.__svd_sparse_lanczos_sfunc m4_ifdef( `__POSTGRESQL__', `', `, prefunc = MADLIB_SCHEMA.__svd_lanczos_prefunc' ) ); --------------------------------------------------------------------- --------Postproc Function for Computing Lanzcos P/V Vectors--------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_pvec ( vector FLOAT8[], -- Partial result from the aggregator pvec FLOAT8[], -- Previous P vector beta FLOAT8 -- Previous beta ) RETURNS MADLIB_SCHEMA.__svd_lanczos_result AS 'MODULE_PATHNAME', 'svd_lanczos_pvec' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_qvec ( vector FLOAT8[], -- Partial result from the aggregator qvec FLOAT8[], -- Previous P vector alpha FLOAT8 -- Previous beta ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_lanczos_qvec' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); --------------------------------------------------------------------- -----------------Gram-Schmidt Orthogonilization---------------------- --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_sfunc ( state FLOAT8[], vec_unorthogonalized FLOAT8[], vec_orthogonalized FLOAT8[] ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_gram_schmidt_orthogonalize_sfunc' LANGUAGE C m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_prefunc ( state1 FLOAT8[], state2 FLOAT8[] ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_gram_schmidt_orthogonalize_prefunc' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); -- This function will also do the normalization CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_ffunc ( state FLOAT8[] ) RETURNS MADLIB_SCHEMA.__svd_lanczos_result AS 'MODULE_PATHNAME', 'svd_gram_schmidt_orthogonalize_ffunc' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); DROP AGGREGATE IF EXISTS MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_agg ( FLOAT8[], -- Unorthogonalized vector FLOAT8[] -- Orthogonalized vector ); CREATE AGGREGATE MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_agg ( FLOAT8[], -- Unorthogonalized vector FLOAT8[] -- Orthogonalized vector ) ( stype = FLOAT8[], sfunc = MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_sfunc, finalfunc = MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_ffunc m4_ifdef( `__POSTGRESQL__', `', `, prefunc = MADLIB_SCHEMA.__svd_gram_schmidt_orthogonalize_prefunc' ) ); --------------------------------------------------------------------- --------------------Lanczos Bidiagonalization------------------------ --------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_bidiagonalize ( source_table TEXT, output_table_prefix TEXT, n_iterations INT, k INT, is_block BOOLEAN ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.lanczos_bidiagonalize(schema_madlib, source_table, output_table_prefix, n_iterations, k, is_block) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_lanczos_bidiagonalize_sparse ( source_table TEXT, row_id TEXT, col_id TEXT, val TEXT, output_table_prefix TEXT, n_iterations INT, k INT ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.lanczos_bidiagonalize_sparse(schema_madlib, source_table, row_id, col_id, val, output_table_prefix, n_iterations, k) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); --------------------------------------------------------------------- -------------------- SVD of Bidiagonal matrix ------------------------ --------------------------------------------------------------------- DROP TYPE IF EXISTS MADLIB_SCHEMA.__svd_bidiagonal_matrix_result CASCADE; CREATE TYPE MADLIB_SCHEMA.__svd_bidiagonal_matrix_result AS ( left_matrix FLOAT8[][], right_matrix FLOAT8[][], singular_values FLOAT8[] ); ------------------------------------------------------------------------------ --The bidiagonal matrix is represented as a triple: --where: -- row_ids is an array of integers representing row_ids of non-zero elements -- col_ids is an array of integers representing col_ids of non-zero elements -- vals is an array of doubles representing values of non-zero elements --Note that we don't need the aggregator to convert the sparse bidiagonal --matrix into a dense matrix ------------------------------------------------------------------------------ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_decompose_bidiag( row_ids INT[], col_ids INT[], vals FLOAT8[] ) RETURNS MADLIB_SCHEMA.__svd_bidiagonal_matrix_result AS 'MODULE_PATHNAME', 'svd_decompose_bidiag' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); ----------------------------------------------------------------------- -- Special Vector-Matrix Multiplication Functions ----------------------------------------------------------------------- /** * Multiplication of a row vector with an in-memory matrix * vector: 1 x l * matrix: l x l * k: Sub-matrix of the size l x k */ CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_vec_mult_matrix( vector FLOAT8[], matrix FLOAT8[][], k INT4 ) RETURNS FLOAT8[] AS 'MODULE_PATHNAME', 'svd_vec_mult_matrix' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); DROP TYPE IF EXISTS MADLIB_SCHEMA.__svd_vec_mat_mult_result CASCADE; CREATE TYPE MADLIB_SCHEMA.__svd_vec_mat_mult_result AS ( row_id INT4, row_vec FLOAT8[] ); --Multiplication of a column vector with an in-memory matrix --Return a set of m row vector of the size 1 * k CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_vec_trans_mult_matrix_internal( vector FLOAT8[], -- m * l row vector matrix FLOAT8[][], -- l * l in-memory matrix col_id INT4, -- Column ID k INT4 -- Specify the size of submatrix l * k ) RETURNS SETOF MADLIB_SCHEMA.__svd_vec_mat_mult_result AS 'MODULE_PATHNAME', 'svd_vec_trans_mult_matrix' LANGUAGE C STRICT m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); --Multiplication of P/Q vectors with Left/Right Singular Matrix of B CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.__svd_vec_trans_mult_matrix( vec_table TEXT, -- P/Q column vectors mat_table TEXT, -- (svd_output).left_matrix/right_matrix k INT4, -- Number of singular values is_left BOOLEAN, -- Left matrix? res_table TEXT -- Result ) RETURNS VOID AS $$ PythonFunctionBodyOnly(`linalg', `svd') with AOControl(False): return svd.svd_vec_trans_mult_matrix(schema_madlib, vec_table, mat_table, k, res_table, is_left) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `MODIFIES SQL DATA', `'); ----------------------------------------------------------------------- -- Help functions ----------------------------------------------------------------------- CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd( input_message TEXT ) RETURNS TEXT AS $$ PythonFunctionBodyOnly(`linalg', `svd') return svd.svd_help_message(schema_madlib, input_message) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `'); CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.svd() RETURNS TEXT AS $$ PythonFunctionBodyOnly(`linalg', `svd') return svd.svd_help_message(schema_madlib, None) $$ LANGUAGE plpythonu m4_ifdef(`__HAS_FUNCTION_PROPERTIES__', `NO SQL', `');