pyfaust.factparams module

The module for configuration structures dedicated to factorization algorithms.

class pyfaust.factparams.ConstraintGeneric(name, num_rows, num_cols, cons_value, normalized=True, pos=False)

This is the parent class for representing a factor constraint in FAuST factorization algorithms.

This class shouldn’t be instantiated, rather rely on sub-classes. Typically, a constraint finds its place into a ParamsFact or sub-class instance (as a container for the factorization parameters). It’s also possible to set a list of constraints with the ConstraintList class.

Attributes:

_name:

The name of the constraint applied to the factor (ConstraintName instance).

_num_rows:

the number of columns of the constrained matrix.

_num_cols:

the number of columns of the constrained matrix.

_cons_value:

The value of the constraint.

See also

ConstraintGeneric.__init__(), ConstraintInt,

ConstraintReal, ConstraintMat, pyfaust.fact.palm4msa(), pyfaust.fact.hierarchical(), ParamsPalm4MSA, ParamsHierarchical.

__init__(name, num_rows, num_cols, cons_value, normalized=True, pos=False)

Constructs a generic constraint.

Warning

This constructor shouldn’t be called directly as the class is

abstract.

Args:

name: (ConstraintName)

The name of the constraint applied to the factor.

num_rows: (int)

the number of columns of the constrained matrix.

num_cols: (int)

the number of columns of the constrained matrix.

cons_value:

The value of the constraint.

Raises:

TypeError: Can’t instantiate abstract class ConstraintGeneric with abstract methods project. This exception is python 3 only, but this class shouldn’t be instantiated in python 2.7 either.

__repr__()

Return repr(self).

__weakref__

list of weak references to the object (if defined)

is_int_constraint()

Returns True if this constraint is a ConstraintInt, False otherwise.

is_mat_constraint()

Returns True if this constraint is a ConstraintMat, False otherwise.

is_real_constraint()

Returns True if this constraint is a ConstraintReal, False otherwise.

property name

Property to access the ConstraintName of the constraint.

abstract project(M)

Applies the constraint to the matrix M.

Note

The project function is also called a proximal operator.

Args:

M: a numpy array, it must be of the same size as set in object attributes self._num_rows, self._num_cols.

Raises:

ValueError: if M.shape and self._num_rows, self._num_cols don’t agree. TypeError: if M is not a numpy.ndarray

Returns:

The proximal operator result as a numpy array.

class pyfaust.factparams.ConstraintInt(name, num_rows, num_cols, cons_value, normalized=True, pos=False)

This class represents an integer constraint on a matrix.

It constrains a matrix by its column/row-vectors sparsity or also called 0-norm: ConstraintName.SPLIN, ConstraintName.SPCOL, ConstraintName.SPLINCOL.

The other constraint names of this type are: ConstraintName.SP, ConstraintName.SP_POS, which both designate the 0-norm based constraint of the matrix with besides for SP_POS the zero replacement of all negative values.

See also

ConstraintInt.__init__()

__init__(name, num_rows, num_cols, cons_value, normalized=True, pos=False)

Args:

name: (ConstraintName or str)

it must be a ConstraintName instance set with a value among SP_POS, SP, SPLIN, SPCOL, SPLINCOL, SPTRIU, SPTRIL, SPSYMM (cf. ConstraintName) or it can also be one of the more handy str aliases which are respectively ‘sppos’, ‘sp’, ‘splin’, ‘spcol’, ‘splincol’, ‘sptriu’, ‘sptril’, ‘spsymm’.

num_rows: (int)

the number of rows of the constrained matrix.

num_cols: (int)

the number of columns of the constrained matrix.

cons_value: (int)

the integer value of the constraint (the 0-norm as sparsity).

Example:

>>> from pyfaust.factparams import ConstraintInt
>>> from numpy.random import rand
>>> import numpy as np
>>> cons = ConstraintInt('sppos', 10, 10, 2) # a short for ConstraintInt(ConstraintName(ConstraintName.SP_POS), 10, 10, 2)
>>> # cons_value == 2 here and this is the 0-norm we want to constrain M to
>>> M = rand(10,10)
>>> np.count_nonzero(M)
100
>>> np.count_nonzero(cons.project(M))
2

See also

ConstraintGeneric.__init__()

project(M)

<b/> See: ConstraintGeneric.project

class pyfaust.factparams.ConstraintList(*args)

A helper class for constructing a list of consistent pyfaust.proj.proj_gen projectors or ConstraintGeneric objects.

Note

ConstraintGeneric use is not advised (these objects are not well

documented). Use rather the projectors functors (from pyfaust.proj module).

Example:

>>> from pyfaust.factparams import ConstraintList
>>> cons = ConstraintList('splin', 5, 500, 32, 'blockdiag',[(10,10), (32,32)], 32, 32);

__add__(other)

Returns the concatenation of two lists (self and other) as a new ConstraintList.

Examples:

>>> from pyfaust.factparams import *
>>> l1 = ConstraintList('normcol', 1, 32, 32, 'sp', 128, 32, 32, 'sp', 128, 32, 32)
>>> l2 = ConstraintList('sp', 128, 32, 32, 'sp', 128, 32, 32)
>>> l1 + l2 
<pyfaust.factparams.ConstraintList object at ...>

__getitem__(ind)

x.__getitem__(y) <==> x[y]

Examples:

>>> from pyfaust.factparams import *
>>> cl = ConstraintList('sp', 128, 32, 32, 'sp', 128, 32, 32)
>>> cl[1]
sp(32, 32, 128)

__init__(*args)

__weakref__

list of weak references to the object (if defined)

class pyfaust.factparams.ConstraintMat(name, cons_value=None, shape=None, normalized=None, pos=False, cons_value_sz=None)

This class represents a matrix-based constraint to apply on a matrix.

See also

ConstraintMat.__init__()

__init__(name, cons_value=None, shape=None, normalized=None, pos=False, cons_value_sz=None)

Constructs a matrix type constraint.

Args:

name: (ConstraintName or str)

must be a ConstraintName instance set with a value among ID, SUPP, CONST, TOEPLITZ or (AANTI)CIRC(ULANT) (cf. ConstraintName) or it can also be one of the more handy str aliases which are respectively: ‘supp’ and ‘const’.

cons_value: (np.ndarray)

the value of the constraint, it must be a numpy.array

shape: (tuple)

the shape of the matrix (only useful for identity prox, ConstraintName.ID. In this case the cons_value argument is None). that defines the constraint (the matrix support for SUPP and the constant matrix for CONST).

normalized: (bool or NoneType)

None because the default value depends on the constraint name (it can be False or True, see ConstraintMat.normalized_default).

Example:

>>> from pyfaust.factparams import ConstraintMat
>>> from numpy.random import rand, seed
>>> from numpy import eye
>>> from numpy.linalg import norm
>>> cons = ConstraintMat('supp', eye(10))
>>> seed(42) # just for reproducibility
>>> M = rand(10,10)
>>> from numpy import count_nonzero
>>> count_nonzero(M)
100
>>> count_nonzero(cons.project(M))
10
>>> from numpy import diag
>>> diag(M)
array([0.37454012, 0.96990985, 0.29214465, 0.94888554, 0.25877998,
       0.92187424, 0.14092422, 0.07404465, 0.88721274, 0.10789143])
>>> diag(cons.project(M))
array([0.19194101, 0.49705083, 0.14971571, 0.48627647, 0.13261728,
       0.47243396, 0.0722196 , 0.03794575, 0.45467094, 0.05529124])
>>> norm(cons.project(M))
1.0

See also

ConstraintGeneric.__init__()

project(M)

See also

ConstraintGeneric.project()

class pyfaust.factparams.ConstraintName(name)

This class defines the names for the sub-types of constraints into the ConstraintGeneric hierarchy of classes.

The table here is a summary of the available constraints.

Attributes:

SP: Designates a constraint on the sparsity/0-norm of a matrix. SPCOL: Designates a sparsity/0-norm constraint on the columns of a matrix. SPLIN: Designates a sparsity/0-norm constraint on the rows of a matrix. SPLINCOL: Designates a constraint that imposes both SPLIN and SPCOL constraints (see example above for clarification). SP_POS: Designates a constraint that imposes a SP constraints and besides set to zero the negative coefficients (it doesn’t apply to complex matrices). SPTRIU : Designates a constraint on the sparsity/0-norm of upper triangular part of a matrix. SPTRIL : Designates a constraint on the sparsity/0-norm of lower triangular part of a matrix. SPSYMM : Designates a constraint on the sparsity/0-norm of a symmetric matrix. NORMCOL: Designates a 2-norm constraint on each column of a matrix. NORMLIN: Designates a 2-norm constraint on each row of a matrix. CONST: Designates a constraint imposing to a matrix to be constant. SUPP: Designates a constraint by a support matrix S (element-wisely multiplying the matrix to constrain to obtain a matrix for which the 2-norm equals 1, see: ConstraintMat.project()). SKPERM: SKPERM prox/constraint. ID: Identity prox/constraint. BLKDIAG: Designates a constraint to produce a block-diagonal matrix (cf. pyfaust.proj.blockdiag). CIRC: Designates a constraint to produce a circulant matrix (cf. pyfaust.proj.circ). ANTICIRC: Designates a constraint to produce an anti-circulant matrix (cf. pyfaust.proj.anticirc). HANKEL: Designates a constraint to produce an anti-circulant matrix (cf. pyfaust.proj.hankel). TOEPLITZ: Designates a constraint to produce a toeplitz matrix (cf. pyfaust.proj.toeplitz). name: The name of the constraint (actually an integer among the valid constants).

Example:

>>> # SPLINCOL Comprehensive Example
>>> # This constraint doesn't necessarily
>>> # lead to a  image matrix with asked sparsity respected
>>> # both for columns and rows
>>> from numpy.random import rand, seed
>>> from numpy.linalg import norm
>>> from pyfaust.factparams import ConstraintInt
>>> import numpy as np
>>> n = 10; m = 10; v = 2;
>>> seed(42) # just for reproducibility
>>> M = rand(10,10)
>>> Mspcol = ConstraintInt('spcol', n, m, v).project(M)
>>> Msplin = ConstraintInt('splin', n, m, v).project(M)
>>> Mp = ConstraintInt('splincol', n, m, v).project(M)
>>> Mp_ = Mspcol + np.where(Mspcol != 0, 0, Msplin) # the sum of Mspcol and Msplin minus their nonzero intersection matrix
>>> Mp_/= norm(Mp_)
>>> # Mp is approximately equal to Mp_
>>> print(norm(Mp-Mp_,2)/norm(Mp_, 2))
0.0041532733089187064
>>> from numpy import count_nonzero
>>> count_nonzero(Mp[:,1])
2
>>> # sparsity value v is not respected
>>> count_nonzero(Mp_[:,1])
2
>>> count_nonzero(Mp_[1,:])
2
>>> count_nonzero(Mp[1,:])
2
>>> # v is respected for this row

__init__(name)

Constructor of the ConstraintName object.

Args:

name: must be a valid constraint name (integer among the static constants defined in the class: ConstraintName.SP, …).

__weakref__

list of weak references to the object (if defined)

is_int_constraint()

A delegate for ConstraintGeneric.is_int_constraint.

is_mat_constraint()

A delegate for ConstraintGeneric.is_mat_constraint.

is_real_constraint()

A delegate for ConstraintGeneric.is_real_constraint.

static name_int2str(_id)

Converts a int constraint short name to its str constant name equivalent.

For example, name_int2str(ConstraintName.SP) returns ‘sp’.

name_str()

Returns the str constant name of this constraint.

static str2name_int(_str)

Converts a str constraint short name to its integer constant name equivalent.

For example, str2name_int(‘sp’) returns ConstraintName.SP.

class pyfaust.factparams.ConstraintReal(name, num_rows, num_cols, cons_value, normalized=False, pos=False)

This class represents a real constraint on a matrix.

It constrains a matrix by a column/row-vector 2-norm (ConstraintName.NORMCOL, ConstraintName.NORMLIN).

See also

ConstraintReal.__init__()

__init__(name, num_rows, num_cols, cons_value, normalized=False, pos=False)

Constructs a real type constraint.

Args:

name: (ConstraintName or str)

must be a ConstraintName instance set with a value among NORMCOL, NORMLIN (cf. ConstraintName) or it can also be one of the more handy str aliases which are respectively: ‘normcol’, ‘normlin’.

num_rows: (int)

the number of columns of the constrained matrix.

num_cols: (int)

the number of columns of the constrained matrix.

cons_value: (float)

the parameter value of the constraint, it must be a float number that designates the 2-norm imposed to all columns (if name is ConstraintName.NORMCOL) or rows (if name is ConstraintName.NORMLIN).

Example:

>>> from pyfaust.factparams import ConstraintReal
>>> from numpy.random import rand, seed
>>> from numpy.linalg import norm
>>> seed(42) # just for reproducibility
>>> cons = ConstraintReal('normcol', 10, 10, 2.) # a short for ConstraintReal(ConstraintName(ConstraintName.NORMCOL), 10, 10, 2.)
>>> M = rand(10,10)*10
>>> norm(M[:,2])
18.91380623771181
>>> norm(cons.project(M)[:,2])
1.9999999999999998

See also

ConstraintGeneric.__init__()

project(M)

See also

ConstraintGeneric.project()

class pyfaust.factparams.MHTPParams(num_its=50, constant_step_size=False, step_size=0.001, palm4msa_period=1000, updating_lambda=True)

This class defines the set of parameters to run the MHTP-PALM4MSA algorithm.

See also

MHTPParams.__init__(), pyfaust.fact.palm4msa_mhtp(), pyfaust.fact.hierarchical_mhtp()

__init__(num_its=50, constant_step_size=False, step_size=0.001, palm4msa_period=1000, updating_lambda=True)

Constructor of the MHTPParams class.

Args:

num_its: (int)

the number of iterations to run the MHTP algorithm.

constant_step_size: (bool)

True to use a constant step for the gradient descent, False otherwise. If False the step size is computed dynamically along the iterations (according to a Lipschitz criterion).

step_size: (float)

The step size used when constant_step_size==True.

palm4msa_period: (int)

The period (in term of iterations) according to the MHTP algorithm is ran (i.e.: 0 <= i < N being the PALM4MSA iteration, MHTP is launched every i = 0 (mod palm4msa_period). Hence the algorithm is ran one time at least – at PALM4MSA iteration 0).

updating_lambda: (bool)

if True then the scale factor of the Faust resulting of the factorization is updated after each iteration of MHTP (otherwise it never changes during the whole MHTP execution).

See also

pyfaust.fact.palm4msa_mhtp(),

pyfaust.fact.hierarchical_mhtp()

__repr__()

The MHTPParams instance str representation.

__weakref__

list of weak references to the object (if defined)

class pyfaust.factparams.ParamsFact(num_facts, is_update_way_R2L, init_lambda, constraints, step_size, constant_step_size, is_verbose, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

The parent abstract class to represent the general factorization parameters.

The class is the base parameters for Palm4MSA and Hierarchical factorization but as an abstract class it’s not for direct use. The documentation is hence left empty, please refer to the subclasses.

Attrs:

DISABLED_OPT: (int)

Optimization disabled (value 0)

INTERNAL_OPT: (int)

Internal optimization (value 1).

EXTERNAL_OPT: (int)

External optimization (value 2)

See also

ParamsHierarchical, ParamsPalm4MSA

__init__(num_facts, is_update_way_R2L, init_lambda, constraints, step_size, constant_step_size, is_verbose, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

See also

ParamsHierarchical.__init__(),

ParamsPalm4MSA.__init__()

__repr__()

Returns object representation.

__weakref__

list of weak references to the object (if defined)

static get_constraints(projs)

Returns a python list of constraints from the projs which is a ConstralintList or a list/tuple that can be a mix of ConstraintGeneric or pyfaust.proj.proj_gen. If projs is a ConstraintList then the function just returns the same object as is.

The function purpose is to make the list uniform as ConstraintGeneric objects.

abstract is_mat_consistent(M)

Verifies a matrix M is shapely consistent to the constraints (it can be factorized according to these constraints).

class pyfaust.factparams.ParamsFactFactory

The factory for creating simplified FAuST hierarchical algorithm parameters (ParamsHierarchical).

Note

this factory is not related to ParamsPalm4MSA, it only creates ParamsHierarchical instances.

See also

ParamsHierarchicalRectMat,

ParamsHierarchicalWHT, pyfaust.fact.hierarchical()

__weakref__

list of weak references to the object (if defined)

static createParams(M, p)

Args:

p: a list ot create a parameter instance.

class pyfaust.factparams.ParamsHierarchical(fact_constraints, res_constraints, stop_crit1, stop_crit2, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_fact_side_left=False, is_verbose=False, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

The parent class to set input parameters for the hierarchical factorization algorithm.

The class’ goal is to instantiate a fully defined set of parameters for the algorithm. But it exists simplified parameterizations for the same algorithm as child classes.

See also

__init__(), ParamsHierarchicalWHT,

ParamsHierarchicalRectMat, pyfaust.fact.hierarchical()

__init__(fact_constraints, res_constraints, stop_crit1, stop_crit2, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_fact_side_left=False, is_verbose=False, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

Constructor.

Args:

fact_constraints: (ConstraintList or list[pyfaust.proj.proj_gen])

to define the constraints of the main factor at each level of the factorization hierarchy (the first one for the first factorization and so on).

res_constraints: (ConstraintList or list[pyfaust.proj.proj_gen]) to define the constraints to apply to the residual factor at each level of the factorization hierarchy (the first one for the first factorization and so on). stop_crit1: (StoppingCriterion)

defines the algorithm stopping criterion for the local optimization of the 2 terms of the last factorization (a main factor and a residual).

stop_crit2: (StoppingCriterion)

a pyfaust.factparams.StoppingCriterion instance which defines the algorithm stopping criterion for the global optimization.

is_update_way_R2L: (bool)

if True pyfaust.fact.palm4msa() (called for each optimization stage) will update factors from the right to the left, otherwise it’s done in reverse order.

init_lambda: (float)

the scale scalar initial value for the global optimization (by default the value is one). It applies only to local optimization at each iteration (the global optimization lambda is updated consequently).

step_size: (float)

the initial step of the PALM descent for both local and global optimization stages.

constant_step_size: (bool)

if True the step_size keeps constant along the algorithm iterations otherwise it is updated before every factor update.

is_fact_side_left: (bool)

if True the leftmost factor is factorized, otherwise it’s the rightmost.

is_verbose: (bool)

True to enable the verbose mode.

factor_format: (str)

‘dynamic’ (by default), ‘dense’, or ‘sparse’. If ‘dense’ or ‘sparse’ then all factors will be respectively numpy.ndarray or scipy.sparse.csr_matrix. If ‘dynamic’ is used then the algorithm determines the format of each factor automatically in order to decrease the memory footprint of the Faust. This option is available only on the 2020 backend pyfaust.fact.palm4msa(), pyfaust.fact.hierarchical() or pyfaust.fact.palm4msa_mhtp(), pyfaust.fact.hierarchical_mhtp().

packing_RL: (bool)

True (by default) to pre-compute R and L products (only available with 2020 backend of pyfaust.fact.hierarchical()).

no_normalization: (bool)

False (by default), if True it disables the normalization of prox output matrix in PALM4MSA algorithm. Note that this option is experimental (only available with 2020 backend of pyfaust.fact.hierarchical()).

no_lambda: (bool)

False (by default), if True it disables the lambda scalar factor in the PALM4MSA algorithm which consists basically to set it always to one (it also lowers the algorithm cost).

norm2_max_iter: (int)

maximum number of iterations of power iteration algorithm. Used for computing 2-norm. norm2_threshold: power iteration algorithm threshold (default to 1e-6). Used for computing 2-norm.

grad_calc_opt_mode: (int)

the mode used for computing the PALM gradient. It can be one value among ParamsFact.EXTERNAL_OPT, ParamsFact.INTERNAL_OPT or ParamsFact.DISABLED_OPT. This parameter is experimental, its value shouln’t be changed.

__repr__()

Returns object representation.

are_constraints_consistent(M)

This method verifies that the constraints are shape-consistent to the matrix/array M to factorize and with each other.

Returns:

True if the constraints are consistent, raises a ValueError otherwise.

is_mat_consistent(M)

Verifies a matrix M is shapely consistent to the constraints (it can be factorized according to these constraints).

class pyfaust.factparams.ParamsHierarchicalDFT(n)

The simplified parameterization class for factorizing a DFT matrix using the hierarchical factorization algorithm.

See also

pyfaust.fact.hierarchical(), __init__()

__init__(n)

Args:

n: (int)

the log2(size) of the DFT matrix (of size 2^n x 2^n).

__repr__()

Returns object representation.

bit_rev_permu(n)

Returns the Bit-reversal permutation of index n.

Args:

n: (int)

the index of the permutation.

Returns: the Bit-reversal permutation of index n as a list.

support_DFT(n)

Generates the DFT supports with the additional bit-reversal permutation matrix.

Args:

n: (int)

the log2(size) of the DFT (of size 2^n x 2^n).

class pyfaust.factparams.ParamsHierarchicalNoResCons(fact_constraints, stop_crit1, stop_crit2, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_fact_side_left=False, is_verbose=False, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

This class is a simplified ParamsHierarchical in which you define only the pyfaust.fact.hierarchical() resulting Faust factors constraints.

You don’t have to define the intermediate residual factors as you normally do with a ParamsHierarchical. With a ParamsHierachicalNoResCons they are defined automatically/internally using pyfaust.proj.proj_id. It means that only the gradient descent of PALM4MSA modify the residual factors. The only residual factor you have to define the constraint for, is the last one (because it is present in the resulting Faust of pyfaust.fact.hierarchical()).

The example below shows (for a Hadamard matrix factorization) the definition of a ParamsHierarchical instance and its simpler equivalent (with the same set of internal defaultly defined residual constraints) as a ParamsHierachicalNoResCons. It allows to get exactly what is exactly a ParamsHierarchicalNoResCons internally. This example is a detailed way to the same thing as ParamsHierarchicalWHTNoResCons.

See also

ParamsHierarchical, pyfaust.fact.hierarchical(),

ParamsHierarchicalNoResCons.__init__()

Example:

This example shows two parameterizations that are equivalent. The first one, p1, is defined through a ParamsHierarchical instance while the second one, p2, is defined using a ParamsHierarchicalNoResCons instance.

>>> from pyfaust import wht
>>> from pyfaust.proj import skperm, proj_id
>>> from pyfaust.factparams import ParamsHierarchical, ParamsHierarchicalNoResCons, StoppingCriterion
>>> from pyfaust.fact import hierarchical
>>> from numpy import log2
>>> from numpy.linalg import norm
>>> # create a Hadamard matrix
>>> H = wht(32).toarray()
>>> d = H.shape[0]
>>> n = int(log2(d))
>>> res_projs = [skperm((d,d), int(d/2**(i+1)), normalized=True) if i == n-2 else proj_id((d,d)) for i in range(n-1)]
>>> fac_projs = [skperm((d,d), 2, normalized=True) for i in range(n-1)]
>>> stop_crit = StoppingCriterion(num_its=30)
>>> p1 = ParamsHierarchical(fac_projs, res_projs, stop_crit, stop_crit, is_update_way_R2L=True, packing_RL=False)
>>> simple_projs = fac_projs+[res_projs[-1]]
>>> p2 = ParamsHierarchicalNoResCons(simple_projs, stop_crit, stop_crit, is_update_way_R2L=True, packing_RL=False)
>>> # p1 and p2 are exactly the same set of parameters for hierarchical
>>> # let's verify the results
>>> # factorizing with p1 (ParamsHierarchical) into Faust F1
>>> F1 = hierarchical(H, p1, backend=2020)
>>> # factorizing with p2 (ParamsHierarchicalNoResCons)
>>> print("F1=", F1)
F1= Faust size 32x32, density 0.3125, nnz_sum 320, 5 factor(s):
- FACTOR 0 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 1 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 2 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 3 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 4 (double) SPARSE, size 32x32, density 0.0625, nnz 64

>>> print("F1 error =", (F1-H).norm()/norm(H))
F1 error = 7.850462159063938e-16
>>> # factorizing with p2 (ParamsHierarchicalNoResCons) into Faust F2
>>> F2 = hierarchical(H, p2, backend=2020)
>>> print("F2=", F2)
F2= Faust size 32x32, density 0.3125, nnz_sum 320, 5 factor(s):
- FACTOR 0 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 1 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 2 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 3 (double) SPARSE, size 32x32, density 0.0625, nnz 64
- FACTOR 4 (double) SPARSE, size 32x32, density 0.0625, nnz 64

>>> print("F2 error =", (F2-H).norm()/norm(H))
F2 error = 7.850462159063938e-16

__init__(fact_constraints, stop_crit1, stop_crit2, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_fact_side_left=False, is_verbose=False, factor_format='dynamic', packing_RL=True, no_normalization=False, no_lambda=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

Constructor.

Args:

fact_constraints: the list of pyfaust.proj.proj_gen or pyfaust.factparams.ConstraintGeneric that define the structure of the pyfaust.fact.hierarchical() resulting Faust factors in the same order if is_fact_side_left==False, in the reverse order otherwise. stop_crit1: cf. pyfaust.fact.ParamsHierarchical.__init__ stop_crit2: cf. pyfaust.fact.ParamsHierarchical.__init__ is_update_way_R2L: cf. pyfaust.fact.ParamsHierarchical.__init__ init_lambda: cf. pyfaust.fact.ParamsHierarchical.__init__ step_size: cf. pyfaust.fact.ParamsHierarchical.__init__ constant_step_size: cf. pyfaust.fact.ParamsHierarchical.__init__ is_fact_side_left: cf. pyfaust.fact.ParamsHierarchical.__init__ is_verbose: cf. pyfaust.fact.ParamsHierarchical.__init__ factor_format: cf. pyfaust.fact.ParamsHierarchical.__init__ packing_RL: cf. pyfaust.fact.ParamsHierarchical.__init__ no_normalization: cf. pyfaust.fact.ParamsHierarchical.__init__ no_lambda: cf. pyfaust.fact.ParamsHierarchical.__init__ norm2_max_iter: cf. pyfaust.fact.ParamsHierarchical.__init__ grad_calc_opt_mode: cf. pyfaust.fact.ParamsHierarchical.__init__

class pyfaust.factparams.ParamsHierarchicalRectMat(m, n, j, k, s, rho=0.8, P=1.4)

The simplified parameterization class for factorizing a rectangular matrix with the hierarchical factorization algorithm (pyfaust.fact.hierarchical).

The parameters m and n are the dimensions of the input matrix.

See also

pyfaust.fact.hierarchical(), pyfaust.demo.bsl,

ParamsHierarchicalRectMat.__init__()

__init__(m, n, j, k, s, rho=0.8, P=1.4)

Constructor for the specialized parameterization used for example in the pyfaust.demo.bsl (brain souce localization).

For a better understanding you might refer to [1].

The figure below describes the sparsity of each factor of the Faust you’ll obtain using pyfaust.fact.hierarchical() with a ParamsHierarchicalRectMat instance.

<img src=”https://faust.inria.fr/files/2022/03/ParamsHierarchicalRectMat_nnz_figure.png” width=”512” height=”264” style=”display:block;margin-left:auto;margin-right:auto”/>

The resulting Faust.nnz_sum is: \(\lceil P m^2 \rho^{j-2} \rceil + (j-2) s m + k n\)

Args:

m: (int)

the number of rows of the input matrix.

n: (int)

the number of columns of the input matrix.

j: (int)

the total number of factors.

k: (int)

the integer sparsity per column (SPCOL, pyfaust.proj.spcol) applied to the rightmost factor (index j-1) of shape (m, n).

s: (int)

s*m is the integer sparsity targeted (SP, pyfaust.proj.sp) for all the factors from the second (index 1) to index j-2. These factors are square of order n.

rho: (float)

defines the integer sparsity (SP, pyfaust.proj.sp) of the i-th residual (i=0:j-2): ceil(P*m**2*rho**i).

P: (float)

defines the integer sparsity of the i-th residual (i=0:j-2): ceil(P*m**2*rho**i).

Example:

>>> from pyfaust.factparams import ParamsHierarchicalRectMat
>>> # set p1 with m, n, j, k parameters
>>> p1 = ParamsHierarchicalRectMat(32, 128, 8, 4, 2)
>>> # now with additional optional rho and P
>>> p2 =  ParamsHierarchicalRectMat(32, 128, 8, 4, 2, rho=.7, P=1.5)

[1] Le Magoarou L. and Gribonval R., “Flexible multi-layer sparse approximations of matrices and applications”, Journal of Selected Topics in Signal Processing, 2016. [https://hal.archives-ouvertes.fr/hal-01167948v1]

static createParams(M, p)

Static member function to create a ParamsHierarchicalRectMat instance by a simplified parameterization expression.

Args:

p: a list of the form [‘rectmat’, j, k, s] or [[‘rectmat’, num_facts, k, s], {‘rho’: rho, ‘P’: P}] to create a parameter instance with the parameters j, k, s and optionally rho and P (see the class constructor ParamsHierarchicalRectMat.__init__ for their definitions).

Example:

>>> from pyfaust.factparams import ParamsHierarchicalRectMat
>>> from numpy.random import rand, seed
>>> seed(42) # just for reproducibility
>>> num_facts = 9
>>> k = 10
>>> s = 8
>>> p = ParamsHierarchicalRectMat.createParams(rand(256, 1024), ['rectmat', num_facts, k, s])
>>> rho = 1.2
>>> P = 1.5
>>> p2 = ParamsHierarchicalRectMat.createParams(rand(256, 1024), [['rectmat', num_facts, k, s], {'rho': rho, 'P': P}])

class pyfaust.factparams.ParamsHierarchicalRectMatNoResCons(m, n, j, k, s, rho=0.8, P=None, **kwargs)

This parameter class is the same as ParamsHierarchicalRectMat except that there is no residual factor constraints (see ParamsHierachicalNoResCons).

See also

pyfaust.fact.hierarchical(), pyfaust.demo.bsl(),

ParamsHierarchicalRectMat, ParamsHierarchicalNoResCons(), ParamsHierarchicalRectMatNoResCons.__init__()

__init__(m, n, j, k, s, rho=0.8, P=None, **kwargs)

This class defines the same parameterization as ParamsHierarchicalRectMat except that there is no constraint on the residual factors (cf. pyfaust.proj.proj_id).

Args:

m: (int)

cf. ParamsHierarchicalRectMat.__init__()

n: (int)

cf. ParamsHierarchicalRectMat.__init__()

j: (int)

cf. ParamsHierarchicalRectMat.__init__()

k: (int)

cf. ParamsHierarchicalRectMat.__init__()

s: (float)

cf. ParamsHierarchicalRectMat.__init__()

rho: (float)

cf. ParamsHierarchicalRectMat.__init__()

P: (float)

cf. ParamsHierarchicalRectMat.__init__()

static createParams(M, p)

Static member function to create a ParamsHierarchicalRectMatNoResCons instance by a simplified parameterization expression.

Args:

p: a list of the form [‘rectmat_simple’, j, k, s] to create a parameter instance with the parameters j, k, s (see the class ParamsHierarchicalRectMat.__init__ for their definitions).

Example:

>>> from pyfaust.factparams import ParamsHierarchicalRectMat
>>> from numpy.random import rand, seed
>>> seed(42) # just for reproducibility
>>> num_facts = 9
>>> k = 10
>>> s = 8
>>> p = ParamsHierarchicalRectMat.createParams(rand(256, 1024), ['rectmat_simple', num_facts, k, s])

class pyfaust.factparams.ParamsHierarchicalSquareMat(n, proj_name='splincol')

This class is deprecated, please use ParamsHierarchicalWHT instead. This class will be removed in a few minor versions of pyfaust.

See also

ParamsHierarchicalWHT.__init__()

__init__(n, proj_name='splincol')

Args:

n: (int)

the number of output factors (the input matrix to factorize must be of shape (2**n, 2**n)).

proj_name: (str)

the type of projector used, must be either ‘splincol’ (default value) or ‘skperm’.

class pyfaust.factparams.ParamsHierarchicalWHT(n, proj_name='splincol')

The simplified parameterization class for factorizing a Hadamard matrix with the hierarchical factorization algorithm.

This type of parameters is typically used for a Hadamard matrix factorization.

See also

pyfaust.fact.hierarchical(), pyfaust.demo.hadamard,

ParamsHierarchicalWHT.__init__()

__init__(n, proj_name='splincol')

Args:

n: (int)

the number of output factors (the input matrix to factorize must be of shape (2**n, 2**n)).

proj_name: (str)

the type of projector used, must be either ‘splincol’ (default value) or ‘skperm’.

class pyfaust.factparams.ParamsHierarchicalWHTNoResCons(n)

The simplified parameterization class for factorizing a Hadamard matrix with the hierarchical factorization algorithm.

This type of parameters is typically used for a Hadamard matrix factorization. This is a variant of ParamsHierarchicalWHT. Here the intermediate residual factors are not constrained at all, the other factors are constrained with pyfaust.proj.skperm.

See also

pyfaust.fact.hierarchical(), pyfaust.demo.hadamard(),

ParamsHierarchicalWHTNoResCons.__init__()

__init__(n)

args:

n: (int)

the number of output factors (the input matrix to factorize must be of shape (2**n, 2**n)).

proj_name: (str)

the type of projector used, must be either ‘splincol’ (default value) or ‘skperm’.

class pyfaust.factparams.ParamsPalm4MSA(constraints, stop_crit, init_facts=None, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_verbose=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

The class intents to set input parameters for the Palm4MSA algorithm.

See also

ParamsPalm4MSA.__init__(), pyfaust.fact.palm4msa

__init__(constraints, stop_crit, init_facts=None, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, constant_step_size=False, is_verbose=False, norm2_max_iter=100, norm2_threshold=1e-06, grad_calc_opt_mode=2, **kwargs)

Constructor.

Args:

constraints: (ConstraintList or list[pyfaust.proj.proj_gen]).

The number of items determines the number of matrix factors.

stop_crit: (pyfaust.factparams.StoppingCriterion)

defines the algorithm stopping criterion.

init_facts: (list`[`np.ndarray or scipy.sparse.csr_matrix])

if defined, pyfaust.fact.palm4msa() will initialize the factors with init_facts (by default, None, implies that the first factor to be updated is initialized to zero and the others to identity. Note that the so called first factor can be the rightmost or the leftmost depending on the is_update_way_R2L argument). Note also that the matrices must be np.ndarray if the backend argument of pyfaust.fact.palm4msa() is equal to 2016, otherwise (backend==2020) it is possible to use np.ndarray or scipy.sparse.csr_matrix (depending of the ParamsPalm4MSA.factor_format attribute).

is_update_way_R2L: (bool)

if True pyfaust.fact.palm4msa() will update factors from the right to the left, otherwise it’s done in reverse order.

init_lambda: (float)

the scale scalar initial value (by default the value is one).

step_size: (float)

the initial step of the PALM descent.

constant_step_size: (bool)

if True the step_size keeps constant along the algorithm iterations otherwise it is updated before every factor update.

is_verbose: (bool)

True to enable the verbose mode.

norm2_max_iter: (float)

maximum number of iterations of power iteration algorithm. Used for computing 2-norm.

norm2_threshold: (float)

power iteration algorithm threshold (default to 1e-6). Used for computing 2-norm.

grad_calc_opt_mode: (float)

the mode used for computing the PALM gradient. It can be one value among pyfaust.factparams.ParamsFact.EXTERNAL_OPT, pyfaust.factparams.ParamsFact.INTERNAL_OPT or pyfaust.factparams.ParamsFact.DISABLED_OPT. This parameter is experimental, its value shouldn’t be changed.

no_normalization: (bool)

False (by default), if True it disables the normalization of prox output matrix in PALM4MSA algorithm. Note that this option is experimental.

no_lambda: (bool)

False (by default), if True it disables the lambda scalar factor in the PALM4MSA algorithm which consists basically to set it always to one (it lowers also the algorithm cost).

__repr__()

Returns object representation.

are_constraints_consistent(M)

This method verifies that the constraints are shape-consistent to the matrix/array M to factorize and with each other.

Returns:

True if the constraints are consistent, raises a ValueError otherwise.

is_mat_consistent(M)

See also

ParamsFact.is_mat_consistent()

class pyfaust.factparams.ParamsPalm4MSAFGFT(constraints, stop_crit, init_facts=None, init_D=None, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, is_verbose=False)

See also

ParamsPalm4MSAFGFT.__init__()

__init__(constraints, stop_crit, init_facts=None, init_D=None, is_update_way_R2L=False, init_lambda=1.0, step_size=1e-16, is_verbose=False)

Constructor.

Args:

constraints: (ConstraintList or list[pyfaust.proj.proj_gen]).

The number of items determines the number of matrix factors.

stop_crit: (pyfaust.factparams.StoppingCriterion)

defines the algorithm stopping criterion.

init_facts: (list`[`np.ndarray or scipy.sparse.csr_matrix])

if defined, pyfaust.fact.palm4msa() will initialize the factors with init_facts (by default, None, implies that the first factor to be updated is initialized to zero and the others to identity. Note that the so called first factor can be the rightmost or the leftmost depending on the is_update_way_R2L argument). Note also that the matrices must be np.ndarray if the backend argument of pyfaust.fact.palm4msa() is equal to 2016, otherwise (backend==2020) it is possible to use np.ndarray or scipy.sparse.csr_matrix (depending of the ParamsPalm4MSA.factor_format attribute).

is_update_way_R2L: (bool)

if True pyfaust.fact.palm4msa() will update factors from the right to the left, otherwise it’s done in reverse order.

init_lambda: (float)

the scale scalar initial value (by default the value is one).

step_size: (float)

the initial step of the PALM descent.

constant_step_size: (bool)

if True the step_size keeps constant along the algorithm iterations otherwise it is updated before every factor update.

is_verbose: (bool)

True to enable the verbose mode.

norm2_max_iter: (float)

maximum number of iterations of power iteration algorithm. Used for computing 2-norm.

norm2_threshold: (float)

power iteration algorithm threshold (default to 1e-6). Used for computing 2-norm.

grad_calc_opt_mode: (float)

the mode used for computing the PALM gradient. It can be one value among pyfaust.factparams.ParamsFact.EXTERNAL_OPT, pyfaust.factparams.ParamsFact.INTERNAL_OPT or pyfaust.factparams.ParamsFact.DISABLED_OPT. This parameter is experimental, its value shouldn’t be changed.

no_normalization: (bool)

False (by default), if True it disables the normalization of prox output matrix in PALM4MSA algorithm. Note that this option is experimental.

no_lambda: (bool)

False (by default), if True it disables the lambda scalar factor in the PALM4MSA algorithm which consists basically to set it always to one (it lowers also the algorithm cost).

class pyfaust.factparams.ParamsPalm4msaWHT(matrix_size)

This class is a simple parameterization of PALM4MSA to factorize a Hadamard matrix using the pyfaust.proj.skperm proximity operator.

Example:

>>> from pyfaust.factparams import ParamsPalm4msaWHT
>>> from pyfaust.fact import palm4msa
>>> from pyfaust import wht
>>> from numpy.linalg import norm
>>> H = wht(128).toarray()
>>> p = ParamsPalm4msaWHT(H.shape[0])
>>> F = palm4msa(H, p)
>>> # Approximation error
>>> err = (F-H).norm()/norm(H)
>>> err < 1e-15
True

Reference:

[1] Quoc-Tung Le, Rémi Gribonval. Structured Support Exploration For Multilayer Sparse Matrix Fac- torization. ICASSP 2021 - IEEE International Conference on Acoustics, Speech and Signal Processing, Jun 2021, Toronto, Ontario, Canada. pp.1-5 hal-03132013.

See also

pyfaust.fact.palm4msa(),

ParamsPalm4msaWHT.__init__()

__init__(matrix_size)

Constructor.

Args:

constraints: (ConstraintList or list[pyfaust.proj.proj_gen]).

The number of items determines the number of matrix factors.

stop_crit: (pyfaust.factparams.StoppingCriterion)

defines the algorithm stopping criterion.

init_facts: (list`[`np.ndarray or scipy.sparse.csr_matrix])

if defined, pyfaust.fact.palm4msa() will initialize the factors with init_facts (by default, None, implies that the first factor to be updated is initialized to zero and the others to identity. Note that the so called first factor can be the rightmost or the leftmost depending on the is_update_way_R2L argument). Note also that the matrices must be np.ndarray if the backend argument of pyfaust.fact.palm4msa() is equal to 2016, otherwise (backend==2020) it is possible to use np.ndarray or scipy.sparse.csr_matrix (depending of the ParamsPalm4MSA.factor_format attribute).

is_update_way_R2L: (bool)

if True pyfaust.fact.palm4msa() will update factors from the right to the left, otherwise it’s done in reverse order.

init_lambda: (float)

the scale scalar initial value (by default the value is one).

step_size: (float)

the initial step of the PALM descent.

constant_step_size: (bool)

if True the step_size keeps constant along the algorithm iterations otherwise it is updated before every factor update.

is_verbose: (bool)

True to enable the verbose mode.

norm2_max_iter: (float)

maximum number of iterations of power iteration algorithm. Used for computing 2-norm.

norm2_threshold: (float)

power iteration algorithm threshold (default to 1e-6). Used for computing 2-norm.

grad_calc_opt_mode: (float)

the mode used for computing the PALM gradient. It can be one value among pyfaust.factparams.ParamsFact.EXTERNAL_OPT, pyfaust.factparams.ParamsFact.INTERNAL_OPT or pyfaust.factparams.ParamsFact.DISABLED_OPT. This parameter is experimental, its value shouldn’t be changed.

no_normalization: (bool)

False (by default), if True it disables the normalization of prox output matrix in PALM4MSA algorithm. Note that this option is experimental.

no_lambda: (bool)

False (by default), if True it disables the lambda scalar factor in the PALM4MSA algorithm which consists basically to set it always to one (it lowers also the algorithm cost).

class pyfaust.factparams.StoppingCriterion(num_its=500, tol=None, maxiter=10000, relerr=False, relmat=None, erreps=None)

This class defines a StoppingCriterion for PALM4MSA algorithms.

A stopping criterion can be of two kinds:

• number of iterations,

• error threshold.

See also

StoppingCriterion.__init__()

__init__(num_its=500, tol=None, maxiter=10000, relerr=False, relmat=None, erreps=None)

Class constructor.

Args:

num_its: (int)

the fixed number of iterations of the algorithm. By default the value is DEFAULT_NUMITS. The constructor will fail if arguments num_its and tol are used together.

tol: (float)

error target according to the algorithm is stopped. The constructor will fail if arguments num_its and tol are used together.

maxiter: (int)

The maximum number of iterations to run the algorithm, whatever is the criterion used (tol or num_its).

relerr: (bool)

if False the tol error defines an absolute error, otherwise it defines a relative error (in this case the ‘relmat’ matrix will be used to convert internally the given ‘tol’ value to the corresponding absolute error).

relmat: (bool)

The matrix against which is defined the relative error. if relerr is True, this argument is mandatory.

erreps: (float)

defines the epsilon on the approximation error between two PALM4MSA iterations. If the error doesn’t improve more than erreps then the algorithm stops (.. warning:: this argument is only supported by the 2020 backend of PALM4MSA implementations).

Example:

>>> from pyfaust.factparams import StoppingCriterion
>>> from numpy.random import rand, seed
>>> seed(42) # just for reproducibility
>>> s = StoppingCriterion()
>>> print(s)
num_its: 500, maxiter: 10000
>>> s = StoppingCriterion(5)
>>> print(s)
num_its: 5, maxiter: 10000
>>> s = StoppingCriterion(tol=.5)
>>> print(s)
tol: 0.5, relerr: False, maxiter: 10000
>>> s = StoppingCriterion(tol=.2, relerr=True, relmat=rand(10,10))
>>> print(s)
tol: 1.1111883397755122, relerr: True, maxiter: 10000

__repr__()

Returns the StoppingCriterion object representation.

__str__()

Converts StoppingCriterion to a str.

__weakref__

list of weak references to the object (if defined)