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

PADDLE-TF algorithm (paddle.tight)

This module implements the PADDLE algorithm for learning a dictionary approximating a tight frame.

As in paddle.dual, there are two main functions:

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

Both uses FISTA acceleration.

Main Functions

paddle.tight.init(X, K, det=False)

Initializes the variables.

Initializes the matrices D 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.

Parameters :

X : (d, N) ndarray

Input data

K : integer

Size of the dictionary

det : bool

If True, the choice of atoms is deterministic

Returns :

D0 : (d, K) ndarray

The initial dictionary

U0 : (K, N) ndarray

The initial encodings

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

Runs the PADDLE-TF algorithm.

The function takes as input the data matrix X, and the initial values for the unknowns D0 and U0.

A function that will be called at each iteration might also be passed as optional argument.

All other optional parameters are passed as keyword arguments.

Parameters :

X : (d, N) ndarray

Input data

D0 : (d, K) ndarray

The initial dictionary

U0 : (K, N) ndarray

The initial encodings

callable : function of type foo(D, 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 frame potential (default 1.0)

mu : float, optional

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

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

U : (K, N) ndarray

The final encodings

full_out : dict

Full output

Inner Optimizations

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

Iterative soft-thresholding with FISTA acceleration.

Minimization of \frac{1}{d}\|X-DU\|_F^2+\frac{2\tau}{K}\|U\|_1 wrt U, that is the well-known LASSO.

Although nearly equivalent to calling paddle.dual._ist with \eta=0, the cost function is different because of the (constant) term from the frame potential.

The function is used by paddle.tight.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

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.tight._pgd(D0, X, U, XUt, UUt, pars, maxiter=500, bound=1)

Projected gradient descent with FISTA acceleration.

Minimization of \|X-DU\|_F^2+\frac{\eta}{d}\|DD^T-\frac{2K}{d} I\|_F^2 wrt D, under additional constraints on the norms of the columns of D. The minimization is performed by alternatively descending along the gradient direction and projecting the columns (rows) of D on the ball with given radius.

The function is used by paddle.tight.learn for the optimization wrt D.

Parameters :

D0 : (d, K) ndarray

Initial value of the unknown

X : (d, N) ndarray

Input data (fixed)

U : (K, N) ndarray

Current encodings (fixed)

XUt : (d, K) ndarray

Part of the gradient

UUt : (K, K) ndarray

Part of the gradient

maxiter : int

Maximum number of iterations allowed (default 500)

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 :

D : (d, K) ndarray

Optimal value of the dictionary

j : int

Number of interations performed

Table Of Contents