1.20.0 User Documentation for Apache MADlib
Low-Rank Matrix Factorization
Contents

This module implements "factor model" for representing an incomplete matrix using a low-rank approximation [1]. Mathematically, this model seeks to find matrices U and V (also referred as factors) that, for any given incomplete matrix A, minimizes:

$\|\boldsymbol A - \boldsymbol UV^{T} \|_2$

subject to $$rank(\boldsymbol UV^{T}) \leq r$$, where $$\|\cdot\|_2$$ denotes the Frobenius norm. Let $$A$$ be a $$m \times n$$ matrix, then $$U$$ will be $$m \times r$$ and $$V$$ will be $$n \times r$$, in dimension, and $$1 \leq r \ll \min(m, n)$$. This model is not intended to do the full decomposition, or to be used as part of inverse procedure. This model has been widely used in recommendation systems (e.g., Netflix [2]) and feature selection (e.g., image processing [3]).

Function Syntax

Low-rank matrix factorization of an incomplete matrix into two factors.

lmf_igd_run( rel_output,
rel_source,
col_row,
col_column,
col_value,
row_dim,
column_dim,
max_rank,
stepsize,
scale_factor,
num_iterations,
tolerance
)


Arguments

rel_output

TEXT. The name of the table to receive the output.

Output factors matrix U and V are in a flattened format.

RESULT AS (
matrix_u    DOUBLE PRECISION[],
matrix_v    DOUBLE PRECISION[],
rmse        DOUBLE PRECISION
);

Features correspond to row i is matrix_u[i:i][1:r]. Features correspond to column j is matrix_v[j:j][1:r].

rel_source

TEXT. The name of the table containing the input data.

The input matrix> is expected to be of the following form:

{TABLE|VIEW} input_table (
row    INTEGER,
col    INTEGER,
value  DOUBLE PRECISION
)

Input is contained in a table that describes an incomplete matrix, with available entries specified as (row, column, value). The input matrix should be 1-based, which means row >= 1, and col >= 1. NULL values are not expected.

col_row
TEXT. The name of the column containing the row number.
col_column
TEXT. The name of the column containing the column number.
col_value
DOUBLE PRECISION. The value at (row, col).
row_dim (optional)
INTEGER, default: "SELECT max(col_row) FROM rel_source". The number of columns in the matrix.
column_dim (optional)
INTEGER, default: "SELECT max(col_col) FROM rel_source". The number of rows in the matrix.
max_rank
INTEGER, default: 20. The rank of desired approximation.
stepsize (optional)
DOUBLE PRECISION, default: 0.01. Hyper-parameter that decides how aggressive the gradient steps are.
scale_factor (optional)
DOUBLE PRECISION, default: 0.1. Hyper-parameter that decides scale of initial factors.
num_iterations (optional)
INTEGER, default: 10. Maximum number if iterations to perform regardless of convergence.
tolerance (optional)
DOUBLE PRECISION, default: 0.0001. Acceptable level of error in convergence.

Examples
1. Prepare an input table/view:
DROP TABLE IF EXISTS lmf_data;
CREATE TABLE lmf_data (
row INT,
col INT,
val FLOAT8
);

2. Populate the input table with some data.
INSERT INTO lmf_data VALUES (1, 1, 5.0);
INSERT INTO lmf_data VALUES (3, 100, 1.0);
INSERT INTO lmf_data VALUES (999, 10000, 2.0);

3. Call the lmf_igd_run() stored procedure.
DROP TABLE IF EXISTS lmf_model;
'lmf_data',
'row',
'col',
'val',
999,
10000,
3,
0.1,
2,
10,
1e-9
);

Example result (the exact result may not be the same).
NOTICE:
Finished low-rank matrix factorization using incremental gradient
DETAIL:
table : lmf_data (row, col, val)
Results:
RMSE = 0.0145966345300041
Output:
view : SELECT * FROM lmf_model WHERE id = 1
lmf_igd_run
-----------
1
(1 row)

4. Sanity check of the result. You may need a model id returned and also indicated by the function lmf_igd_run(), assuming 1 here:
SELECT array_dims(matrix_u) AS u_dims, array_dims(matrix_v) AS v_dims
FROM lmf_model
WHERE id = 1;

Result:
     u_dims    |     v_dims
--------------+----------------
[1:999][1:3] | [1:10000][1:3]
(1 row)

5. Query the result value.
SELECT matrix_u[2:2][1:3] AS row_2_features
FROM lmf_model
WHERE id = 1;

Example output (the exact result may not be the same):
                       row_2_features
---------------------------------------------------------
{{1.12030523084104,0.522217971272767,0.0264869043603539}}
(1 row)

6. Make prediction of a missing entry (row=2, col=7654).
SELECT madlib.array_dot(
matrix_u[2:2][1:3],
matrix_v[7654:7654][1:3]
) AS row_2_col_7654
FROM lmf_model
WHERE id = 1;

Example output (the exact result may not be the same due the randomness of the algorithm):
   row_2_col_7654
------------------
1.3201582940851
(1 row)


Literature

[1] N. Srebro and T. Jaakkola. “Weighted Low-Rank Approximations.” In: ICML. Ed. by T. Fawcett and N. Mishra. AAAI Press, 2003, pp. 720–727. isbn: 1-57735-189-4.

[2] Simon Funk, Netflix Update: Try This at Home, December 11 2006, http://sifter.org/~simon/journal/20061211.html

[3] J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma. “Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization.” In: NIPS. Ed. by Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta. Curran Associates, Inc., 2009, pp. 2080–2088. isbn: 9781615679119.