SlipGURU Dipartimento di Informatica e Scienze dell'Informazione Università Degli Studi di Genova

PADDLE algorithm (paddle.dual)

This module implements the PADDLE algorithm for learning a dictionary and its dual.

There are two main functions:

The algorithm uses other routines, in particular two driving the three inner optimizations:

Both uses FISTA acceleration. Also non-accelerated version, using fixed stepsizes, are available, though not used by paddle.dual.learn:

Main Functions

paddle.dual.init(X, K, det=False, rnd=False)

Initializes the variables.

Initializes the matrices D, C and U from the data matrix X. The dimension of the dictionary is K. If det is True the first K columns of X are chosen as atoms (deterministic initialization), otherwise they are picked randomly. The atoms are normalized to one. The matrix U is chosen as to minimize the reconstruction error. The matrix C is chosen as the pseudo-inverse of D, with rows normalized to one.

Parameters :

X : (d, N) ndarray

Input data

K : integer

Size of the dictionary

det : bool

If True, the choice of atoms is deterministic

rnd : bool

If True, the atoms are not sampled from the examples, but have random values

Returns :

D0 : (d, K) ndarray

The initial dictionary

C0 : (K, d) ndarray

The initial dual

U0 : (K, N) ndarray

The initial encodings

paddle.dual.learn(X, D0, C0, U0, callable=None, **kwargs)

Runs the PADDLE algorithm.

The function takes as input the data matrix X, the initial values for the three unknowns, D0 C0 and U0, and a dictionary of parameters.

The optional parameters are passed as keyword arguments.

Parameters :

X : (d, N) ndarray

Input data

D0 : (d, K) ndarray

The initial dictionary

C0 : (K, d) ndarray

The initial dual

U0 : (K, N) ndarray

The initial encodings

callable : function of type foo(D, C, U, X)

If not None, it gets called at each iteration and the result is appended in an item of full_output

tau : float, optional

Weight of the sparsity penalty (default 0.1)

eta : float, optional

Weight of the coding error (default 1.0)

mu : float, optional

Weight of the l2 penalty on the coefficients (default 0.0)

nnU : bool, optional

Adds a non-negativity constraint on U (default False)

nnD : bool, optional

Adds a non-negativity constraint on U (default False)

maxiter : int, optional

Maximum number of outer iterations (default 10)

minused : integer, optional

Minimum number of times an atom as to be used (default 1)

verbose : bool, optional

Enables verbose output (default False)

rtol : float, optional

Relative tolerance checking convergence (default 1.e-4)

save_dict : bool, optional

If true, the dictionary is saved after each outer iteration (default False)

save_path : str, optional

The path in which to save the dictionary (relevant only if save_dict is True, default ”./”)

save_sorted : bool, optional

If true and if save_dict is also True, the atoms of dictionary are sorted wrt the usage in the sparse coding before being displayed and saved (default False)

save_shape: integer pair, optional :

Numbers of (rows,cols) used to display the atoms of the dictionary (default (10,10))

Returns :

D : (d, K) ndarray

The final dictionary

C : (K, d) ndarray

The final dual

U : (K, N) ndarray

The final encodings

full_out : dict

Full output

Inner Optimizations

paddle.dual._ist(X, U0, D, C, pars, maxiter=1000)

Iterative soft-thresholding with FISTA acceleration.

Minimization of \frac{1}{d}\|X-DU\|_F^2+\frac{\eta}{K}\|U-CX\|_F^2+\frac{2\tau}{K}\|U\|_1 wrt U. When \eta=0 the functional reduces to the well-known LASSO.

The function is used by paddle.dual.learn for the optimization wrt U.

Parameters :

X : (d, N) ndarray

Data matrix

U0 : (K, N) ndarray

Initial value of the unknown

D : (d, K) ndarray

Dictionary

C : (K, d) ndarray

Dual of the dictionary

pars : dict

Optional parameters

maxiter : int

Maximum number of iterations allowed (default 500)

Returns :

U : (K, N) ndarray

Optimal value of the unknown

full_out : dict

Full output

paddle.dual._pgd(Y0, ABt, BBt, cost, maxiter=500, axis=0, bound=1, verbose=False, rtol=0.0001, nn=False)

Projected gradient descent with FISTA acceleration.

Minimization of \|A-YB\|_F^2 wrt Y, under additional constraints on the norms of the columns (or the rows) of Y. The minimization is performed by alternatively descending along the gradient direction AB^T-YBB^T and projecting the columns (rows) of Y on the ball with given radius.

The function is used by paddle.dual.learn for the optimization wrt D and C. In the former case, A and B are X and U, respectively, while in the latter the roles are swapped.

Parameters :

Y0 : (a1, a2) ndarray

Initial value of the unknown

ABt : (a1, a2) ndarray

Part of the gradient

BBt : (a2, a2) ndarray

Part of the gradient

cost : function of type foo(Y)

Evaluates the cost function

maxiter : int

Maximum number of iterations allowed (default 500)

axis : int

Dimension of Y along which the constraint is active (0 for cols, 1 for rows, default is 0)

bound : float

Value of the constraint on the norms of the columns/rows of Y (default is 1)

verbose : bool

If True displays the value of the cost function at each iteration (default is False)

rtol : float

Relative tolerance for convergence criterion

Returns :

Y : () ndarray

Optimal value of the unknown

j : int

Number of interations performed

paddle.dual._ist_fixed(X, U0, D, C, pars, maxiter=1000)

Iterative soft-thresholding with fixed step-size.

Minimization of \frac{1}{d}\|X-DU\|_F^2+\frac{\eta}{K}\|U-CX\|_F^2+\frac{2\tau}{K}\|U\|_1 wrt U. When \eta=0 the functional reduces to the well-known LASSO.

This function is curently noy used. The main function paddle.dual.learn uses its FISTA-accelerated counterpart paddle.dual._pgd.

Parameters :

X : (d, N) ndarray

Data matrix

U0 : (K, N) ndarray

Initial value of the unknown

D : (d, K) ndarray

Dictionary

C : (K, d) ndarray

Dual of the dictionary

pars : dict

Optional parameters

maxiter : int

Maximum number of iterations allowed (default 500)

Returns :

U : (K, N) ndarray

Optimal value of the unknown

full_out : dict

Full output

paddle.dual._pgd_fixed(A0, X, U, B, G2, cost, maxiter=500, pars=None, sigma=None, axis=0, bound=1)

Projected gradient descent with fixed stepsize.

Table Of Contents