pyttb.cp_apr

Non-negative CP decomposition with alternating Poisson regression.

pyttb.cp_apr.cp_apr(input_tensor: tensor | sptensor, rank: int, algorithm: Literal['mu', 'pdnr', 'pqnr'] = 'mu', stoptol: float = 1e-4, stoptime: float = 1e6, maxiters: int = 1000, init: ktensor | Literal['random'] = 'random', maxinneriters: int = 10, epsDivZero: float = 1e-10, printitn: int = 1, printinneritn: int = 0, kappa: float = 0.01, kappatol: float = 1e-10, epsActive: float = 1e-8, mu0: float = 1e-5, precompinds: bool = True, inexact: bool = True, lbfgsMem: int = 3) → Tuple[ktensor, ktensor, Dict][source]

Compute non-negative CP with alternating Poisson regression.

Parameters:

  • input_tensor (pyttb.tensor or pyttb.sptensor)

  • rank (int) – Rank of the decomposition

  • algorithm (str) – in {‘mu’, ‘pdnr, ‘pqnr’}

  • stoptol (float) – Tolerance on overall KKT violation

  • stoptime (float) – Maximum number of seconds to run

  • maxiters (int) – Maximum number of iterations

  • init (str or pyttb.ktensor) – Initial guess

  • maxinneriters (int) – Maximum inner iterations per outer iteration

  • epsDivZero (float) – Safeguard against divide by zero

  • printitn (int) – Print every n outer iterations, 0 for none

  • printinneritn (int) – Print every n inner iterations

  • kappa (int) – MU ALGORITHM PARAMETER: Offset to fix complementary slackness

  • kappatol – MU ALGORITHM PARAMETER: Tolerance on complementary slackness

  • epsActive (float) – PDNR & PQNR ALGORITHM PARAMETER: Bertsekas tolerance for active set

  • mu0 (float) – PDNR ALGORITHM PARAMETER: Initial Damping Parameter

  • precompinds (bool) – PDNR & PQNR ALGORITHM PARAMETER: Precompute sparse tensor indices

  • inexact (bool) – PDNR ALGORITHM PARAMETER: Compute inexact Newton steps

  • lbfgsMem (int) – PQNR ALGORITHM PARAMETER: Precompute sparse tensor indices

Returns:

  • M (pyttb.ktensor) – Resulting ktensor from CP APR

  • Minit (pyttb.ktensor) – Initial Guess

  • output (dict) – Additional output #TODO document this more appropriately

pyttb.cp_apr.tt_cp_apr_mu(input_tensor: tensor | sptensor, rank: int, init: ktensor, stoptol: float, stoptime: float, maxiters: int, maxinneriters: int, epsDivZero: float, printitn: int, printinneritn: int, kappa: float, kappatol: float) → Tuple[ktensor, Dict][source]

Compute nonnegative CP with alternating Poisson regression.

Parameters:

  • input_tensor (pyttb.tensor or pyttb.sptensor)

  • rank (int) – Rank of the decomposition

  • init (pyttb.ktensor) – Initial guess

  • stoptol (float) – Tolerance on overall KKT violation

  • stoptime (float) – Maximum number of seconds to run

  • maxiters (int) – Maximum number of iterations

  • maxinneriters (int) – Maximum inner iterations per outer iteration

  • epsDivZero (float) – Safeguard against divide by zero

  • printitn (int) – Print every n outer iterations, 0 for none

  • printinneritn (int) – Print every n inner iterations

  • kappa (int) – MU ALGORITHM PARAMETER: Offset to fix complementary slackness

  • kappatol – MU ALGORITHM PARAMETER: Tolerance on complementary slackness

Notes

REFERENCE: E. C. Chi and T. G. Kolda. On Tensors, Sparsity, and Nonnegative Factorizations, arXiv:1112.2414 [math.NA], December 2011, URL: http://arxiv.org/abs/1112.2414. Submitted for publication.

pyttb.cp_apr.tt_cp_apr_pdnr(input_tensor: tensor | sptensor, rank: int, init: ktensor, stoptol: float, stoptime: float, maxiters: int, maxinneriters: int, epsDivZero: float, printitn: int, printinneritn: int, epsActive: float, mu0: float, precompinds: bool, inexact: bool) → Tuple[ktensor, Dict][source]

Compute nonnegative CP with alternating Poisson regression.

Computes an estimate of the best rank-R CP model of a tensor X using an alternating Poisson regression. The algorithm solves “row subproblems” in each alternating subproblem, using a Hessian of size R^2.

Parameters:

  • input_tensor (Union[pyttb.tensor,:class:pyttb.sptensor])

  • rank (int) – Rank of the decomposition

  • init (str or pyttb.ktensor) – Initial guess

  • stoptol (float) – Tolerance on overall KKT violation

  • stoptime (float) – Maximum number of seconds to run

  • maxiters (int) – Maximum number of iterations

  • maxinneriters (int) – Maximum inner iterations per outer iteration

  • epsDivZero (float) – Safeguard against divide by zero

  • printitn (int) – Print every n outer iterations, 0 for none

  • printinneritn (int) – Print every n inner iterations

  • epsActive (float) – PDNR & PQNR ALGORITHM PARAMETER: Bertsekas tolerance for active set

  • mu0 (float) – PDNR ALGORITHM PARAMETER: Initial Damping Parameter

  • precompinds (bool) – PDNR & PQNR ALGORITHM PARAMETER: Precompute sparse tensor indices

  • inexact (bool) – PDNR ALGORITHM PARAMETER: Compute inexact Newton steps

Returns:

# TODO detail return dictionary

Notes

REFERENCE: Samantha Hansen, Todd Plantenga, Tamara G. Kolda. Newton-Based Optimization for Nonnegative Tensor Factorizations, arXiv:1304.4964 [math.NA], April 2013, URL: http://arxiv.org/abs/1304.4964. Submitted for publication.

pyttb.cp_apr.tt_cp_apr_pqnr(input_tensor: tensor | sptensor, rank: int, init: ktensor, stoptol: float, stoptime: float, maxiters: int, maxinneriters: int, epsDivZero: float, printitn: int, printinneritn: int, epsActive: float, lbfgsMem: int, precompinds: bool) → Tuple[ktensor, Dict][source]

Compute nonnegative CP with alternating Poisson regression.

tt_cp_apr_pdnr computes an estimate of the best rank-R CP model of a tensor X using an alternating Poisson regression. The algorithm solves “row subproblems” in each alternating subproblem, using a Hessian of size R^2. The function is typically called by cp_apr.

The model is solved by nonlinear optimization, and the code literally minimizes the negative of log-likelihood. However, printouts to the console reverse the sign to show maximization of log-likelihood.

Parameters:

  • input_tensor – Tensor to decompose

  • rank (int) – Rank of the decomposition

  • init – Initial guess

  • stoptol – Tolerance on overall KKT violation

  • stoptime – Maximum number of seconds to run

  • maxiters – Maximum number of iterations

  • maxinneriters – Maximum inner iterations per outer iteration

  • epsDivZero – Safeguard against divide by zero

  • printitn – Print every n outer iterations, 0 for none

  • printinneritn – Print every n inner iterations

  • epsActive – PDNR & PQNR ALGORITHM PARAMETER: Bertsekas tolerance for active set

  • lbfgsMem – Number of vector pairs to store for L-BFGS

  • precompinds – Precompute sparse tensor indices

Returns:

# TODO detail return dictionary

Notes

REFERENCE: Samantha Hansen, Todd Plantenga, Tamara G. Kolda. Newton-Based Optimization for Nonnegative Tensor Factorizations, arXiv:1304.4964 [math.NA], April 2013, URL: http://arxiv.org/abs/1304.4964. Submitted for publication.

pyttb.cp_apr.tt_calcpi_prowsubprob(Data: sptensor, Model: ktensor, rank: int, factorIndex: int, ndims: int, isSparse: Literal[True], sparse_indices: ndarray) → ndarray[source]
pyttb.cp_apr.tt_calcpi_prowsubprob(Data: tensor, Model: ktensor, rank: int, factorIndex: int, ndims: int, isSparse: Literal[False]) → ndarray

Compute Pi for a row subproblem.

Parameters:

  • Data – Tensor to compute subproblem for.

  • isSparse – Flag to determine if sparse subproblem.

  • Model – Current decomposition.

  • rank – Rank of solution.

  • factorIndex – Which factor to solve

  • ndims – Number of dimensions

  • sparse_indices – Indices of row subproblem nonzero elements

Returns:

Pi (numpy.ndarray)

See also

pyttb.calculate_pi

pyttb.cp_apr.calc_partials(isSparse: bool, Pi: ndarray, epsilon: float, data_row: ndarray, model_row: ndarray) → Tuple[ndarray, ndarray][source]

Compute derivative quantities for a PDNR row subproblem.

Parameters:

  • isSparse – Flag if sparse subproblem.

  • Pi

  • epsilon – Prevent division by zero.

  • data_row – Row of data for subproblem.

  • model_row – Row of model for subproblem.

Returns:

  • phi_row (numpy.ndarray) – gradient of row subproblem, except for a constant n \(phi\_row[r] = \sum_{j=1}^{J_n}\frac{x_j\pi_{rj}}{\sum_i^R b_i\pi_{ij}}\)

  • ups_row (numpy.ndarray) – intermediate quantity (upsilon) used for second derivatives n \(ups\_row[j] = \frac{x_j}{\left(\sum_i^R b_i\pi_{ij}\right)^2}\)

pyttb.cp_apr.get_search_dir_pdnr(Pi: ndarray, ups_row: ndarray, rank: int, gradModel: ndarray, model_row: ndarray, mu: float, epsActSet: float) → Tuple[ndarray, ndarray][source]

Compute the search direction using a two-metric projection with damped Hessian.

Parameters:

  • Pi

  • ups_row – intermediate quantity (upsilon) used for second derivatives

  • rank – number of variables for the row subproblem

  • gradModel – gradient vector for the row subproblem

  • model_row – vector of variables for the row subproblem

  • mu – damping parameter

  • epsActSet – Bertsekas tolerance for active set determination

Returns:

pyttb.cp_apr.tt_linesearch_prowsubprob(direction: ndarray, grad: ndarray, model_old: ndarray, step_len: float, step_red: float, max_steps: int, suff_decr: float, isSparse: bool, data_row: ndarray, Pi: ndarray, phi_row: ndarray, display_warning: bool) → Tuple[ndarray, float, float, float, int][source]

Perform a line search on a row subproblem.

Parameters:

  • direction – search direction

  • grad – gradient vector a model_old

  • model_old – current variable values

  • step_len – initial step length, which is the maximum possible step length

  • step_red – step reduction factor (suggest 1/2)

  • max_steps – maximum number of steps to try (suggest 10)

  • suff_decr – sufficient decrease for convergence (suggest 1.0e-4)

  • isSparse – sparsity flag for computing the objective

  • data_row – row subproblem data, for computing the objective

  • Pi – Pi matrix, for computing the objective

  • phi_row – 1-grad, more accurate if failing over to multiplicative update

  • display_warning – Flag to display warning messages or not

Returns:

  • m_new (numpy.ndarray) – new (improved) model values

  • num_evals (int) – number of times objective was evaluated

  • f_old (float) – objective value at model_old

  • f_1 (float) – objective value at model_old + step_len*direction

  • f_new (float) – objective value at model_new

pyttb.cp_apr.get_hessian(upsilon: ndarray, Pi: ndarray, free_indices: ndarray) → ndarray[source]

Return the Hessian for one PDNR row subproblem of Model[n].

Only for just the rows and columns corresponding to the free variables.

Parameters:

  • upsilon – intermediate quantity (upsilon) used for second derivatives

  • Pi

  • free_indices

Returns:

Hessian (numpy.ndarray) – Sub-block of full Hessian identified by free-indices

pyttb.cp_apr.tt_loglikelihood_row(isSparse: bool, data_row: ndarray, model_row: ndarray, Pi: ndarray) → float[source]

Compute log-likelihood of one row subproblem.

Parameters:

  • isSparse – Sparsity flag

  • data_row – vector of data values

  • model_row – vector of model values

  • Pi

Notes

The row subproblem for a given mode includes one row of matricized tensor data (x) and one row of the model (m) in the same matricized mode. Then (dense case) m: R-length vector x: J-length vector Pi: R x J matrix (sparse case) m: R-length vector x: p-length vector, where p = nnz in row of matricized data tensor Pi: R x p matrix F = - (sum_r m_r - sum_j x_j * log (m * Pi_j) where Pi_j denotes the j^th column of Pi NOTE: Rows of Pi’ must sum to one

Returns:

loglikelihood (float) – See notes for description

pyttb.cp_apr.get_search_dir_pqnr(model_row: ndarray, gradModel: ndarray, epsActSet: float, delta_model: ndarray, delta_grad: ndarray, rho: ndarray, lbfgs_pos: int, iters: int, disp_warn: bool) → ndarray[source]

Compute the search direction by projecting with L-BFGS.

Parameters:

  • model_row – current variable values

  • gradModel – gradient at model_row

  • epsActSet – Bertsekas tolerance for active set determination

  • delta_model – L-BFGS array of variable deltas

  • delta_grad – L-BFGS array of gradient deltas

  • rho

  • lbfgs_pos – pointer into L-BFGS arrays

  • iters

  • disp_warn

Returns:

direction (numpy.ndarray) – Search direction based on current L-BFGS and grad

Notes

Adapted from MATLAB code of Dongmin Kim and Suvrit Sra written in 2008. Modified extensively to solve row subproblems and use a better linesearch; for details see REFERENCE: Samantha Hansen, Todd Plantenga, Tamara G. Kolda. Newton-Based Optimization for Nonnegative Tensor Factorizations, arXiv:1304.4964 [math.NA], April 2013, URL: http://arxiv.org/abs/1304.4964. Submitted for publication.

pyttb.cp_apr.calc_grad(isSparse: bool, Pi: ndarray, eps_div_zero: float, data_row: ndarray, model_row: ndarray) → Tuple[ndarray, ndarray][source]

Compute the gradient for a PQNR row subproblem.

Parameters:

  • isSparse

  • Pi

  • eps_div_zero

  • data_row

  • model_row

Returns:

  • phi_row

  • grad_row

pyttb.cp_apr.calculate_pi(Data: sptensor | tensor, Model: ktensor, rank: int, factorIndex: int, ndims: int) → ndarray[source]

Calculate Pi matrix.

Parameters:

  • Data

  • Model

  • rank

  • factorIndex

  • ndims

Returns:

Pi

pyttb.cp_apr.calculate_phi(Data: sptensor | tensor, Model: ktensor, rank: int, factorIndex: int, Pi: ndarray, epsilon: float) → ndarray[source]

Calculate Phi.

Parameters:

  • Data

  • Model

  • rank

  • factorIndex

  • Pi

  • epsilon

pyttb.cp_apr.tt_loglikelihood(Data: tensor | sptensor, Model: ktensor) → float[source]

Compute log-likelihood of data with model.

Parameters:

  • Data

  • Model

Returns:

loglikelihood –

  • (sum_i m_i - x_i * log_i) with i as a multiindex across all tensor dimensions

Notes

We define for any x 0*log(x)=0, such that if our true data is 0 the loglikelihood

is the value of the model.

pyttb.cp_apr.vectorize_for_mu(matrix: ndarray) → ndarray[source]

Unravel matrix into vector.

Parameters:

matrix

Returns:

matrix – Unraveled matrix len(matrix.shape)==1