Discriminative dictionary Learning Toolbox for Classification.

This repository is under construction

• SRC: Sparse Representation-based Classification [1].

• ODL: Online dictionary Learning [2].

• LCKSVD: Label consistent K-SVD[^fn_lcksvd] [3].

• FDDL: Fisher discrimination dictionary learning [4].

• DLSI: dictionary Learning with Structured Incoherence [5]

• DFDL: Discriminative Feature-Oriented dictionary Learning [6]

• DLCOPAR [7]

• LRSDL: Low-rank Shared dictionary Learning [9].

Notation

• Y: signals.
• D: dictionary.
• X: sparse coefficient.
• d: signal dimension. d = size(Y, 1).
• C: number of classes.
• c: class index.
• n_c: number of training samples in class c. Typically, all n_c are the same and equal to n.
• N: total number of training samples.
• Y_range: an array storing range of each class, suppose that labels are sorted in a ascending order. Example: If Y_range = [0, 10, 25], then:
  • There are two classes, samples from class 1 range from 1 to 10, from class 2 range from 11 to 25.
  • In general, samples from class c range from Y_range(c) + 1 to Y_range(c+1)
  • We can observe that number of classes C = numel(Y_range) - 1.
• k_c: number of bases in class-specific dictionary c. Typically, all n_c are the same and equal to k.
• k_0: number of bases in the shared-dictionary
• K: total number of dictionary bases.
• D_range: similar to Y_range but used for dictionary without the shared dictionary.

Supporting functions

All of the following functions are located in subfolder utils.

get_block_col

• Extract a block of columns from a matrix.
• Syntax: Mc = get_block_col(M, c, col_range)
  • M: the big matrix M = [M_1, M_2, ...., M_C].
  • c: block index.
  • col_range: range of samples, see Y_range and D_range above.
• Example: M has 25 columns and col_range = [0, 10, 25], then get_block_col(M, 1, col_range) will output the first block of M, i.e. M(:, 1:10).

get_block_row

• Extract a block of rows from a matrix.
• Syntax: Mc = get_block_row(M, c, row_range)
  • M: the big matrix M = [M_1; M_2; ....; M_C].
  • c: block index.
  • row_range: range of samples, see Y_range and D_range above.
• Example: M has 40 rows and row_range = [0, 10, 25, 40], then get_block_row(M, 2, row_range) will output the second block of M, i.e. M(11:25, :).

get_block

• Extract a submatrix of a matrix
• Syntax: Mij = get_block(M, i, j, row_range, col_range)
  • M the big matrix: M = [ M11, M12, ..., M1m; M21, M22, ..., M2m; ... ; Mn1, Mn2,..., Mnm]
  • i: row block index
  • j: column block index
  • row_range: row range
  • col_range: columns range
• Note: get_block(M, i, j, row_range, col_range) = get_block_col(get_block_row(M, i, row_range), j, col_range).

label_to_range

• Convert from Labels to Ranges
• Example: if label = [1 1 1 2 2 2 2 3 3], then range = [0, 3, 7, 9].
• Syntax: range = label_to_range(label)

range_to_label

• Convert from Ranges to Labels
• Example: if range = [0, 3, 5]`` then label = [1 1 1 2 2]``
• Syntax: label = range_to_label(range)

norm1

• Return norm 1 of a matrix, which is sum of absolute value of all element of that matrix.
• Syntax: res = norm1(X)

normF2

• Return square of the Frobenius norm, which is sum of square of all elements in a matrix
• Syntax: res = normF2(X)

normc

• Normalize columns of a matrix: norm 2 of each columns equals to 1. This function is a built-in function in some recent MATLAB version.
• Syntax: M1 = normc(M1)

vec

• Vectorization of a matrix. This function is a built-in function in some recent MATLAB version.
• Syntax: a = vec(A)

nuclearnorm

• Return nuclear norm of a matrix.
• Syntax res = nuclearnorm(X)
• `

erase_diagonal

• function A = erase_diagonal(A)
• Erase diagonal of a matrix A
• required: size(A, 1) == size(A, 2)

double_diagonal

• function A = double_diagonal(A)
• Double diagonal elements of a matrix A
• required: size(A, 1) == size(A, 2)

erase_diagonal_blocks

• function A = erase_diagonal_blocks(A, row_range, col_range)
• Erase diagonal blocks of a block matrix A whose row range and col range are row_range and col_range
• required: `numel(row_range) == numel(col_range)

double_diagonal_blocks

• function A = double_diagonal_blocks(A, row_range, col_range)
• Double diagonal blocks of a block matrix A whose row range and col range are row_range and col_range
• requirements: numel(row_range0 == numel(col_range))

shrinkage

• Soft thresholding function.
• Syntax: X = shrinkage(U, lambda)
• Solve the following optimization problem: X = arg min_X 0.5*||X - U||_F^2 + lambda||X||_1 where U and X are matrices with same sizes. lambda can be either positive a scalar or a positive matrix (all elements are positive) with same size as X. In the latter case, it is a weighted problem.

shrinkage_rank

• Singular value thresholding algorithm for matrix completion [10].
• Syntax: Y = shrinkage_rank(D, lambda)
• Solve the following optimization problem: X = arg min_X 0.5*||X - U||_F^2 + lambda*||X||_* where ||X||_* is the nuclear norm.

fista

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[11].
• Solve the problem: X = arg min_X F(X) = f(X) + lambda||X||_1 where:
  • X: variable, can be a matrix.
  • f(X) is a smooth convex function with continuously differentiable with Lipschitz continuous gradient L(f) (Lipschitz constant of the gradient of f).
• Syntax: [X, iter] = fista(grad, Xinit, L, lambda, opts, calc_F) where:
  • INPUT:
    • grad: a function calculating gradient of f(X) given X.
    • Xinit: initial guess.
    • L: the Lipschitz constant of the gradient of f(X).
    • lambda: a regularization parameter, can be either a positive scalar or a weighted matrix.
    • opts: a structure variable describing the algorithm.
      • opts.max_iter: maximum iterations of the algorithm. Default 300.
      • opts.tol: a tolerance, the algorithm will stop if difference between two successive X is smaller than this value. Default 1e-8.
      • opts.show_progress: showing F(X) after each iteration or not. Default false.
    • calc_F: optional, a function calculating value of F at X via feval(calc_F, X).
  • OUTPUT:
    • X: solution.
    • iter: number of iterations.

lasso_fista

• Syntax: [X, iter] = lasso_fista(Y, D, Xinit, lambda, opts)
• Solving a Lasso problem using FISTA [11]: X = arg min_X 0.5*||Y - DX||_F^2 + lambda||X||_1. Note that lambda can be either a positive scalar or a matrix with positive elements.
  • INPUT:
    • Y, D, lambda: as in the problem.
    • Xinit: Initial guess
    • opts: options. See also fista
  • OUTPUT:
    • X: solution.
    • iter: number of fistat iterations.
• Note:
  • To see a toy example, un this function without inputs
  • Can be used for solving a Weighted Lasso problem.

SRC

• Sparse Representation-based classification implementation [1].
• Folder SRC.

SRC_pred

• Classification based on SRC.
• Syntax: [pred, X] = SRC_pred(Y, D, D_range, opts)
  • INPUT:
    • Y: test samples.
    • D: the total dictionary. D = [D_1, D_2, ..., D_C] with D_c being the c-th class-specific dictionary.
    • D_range: range of class-specific dictionaries in D. See also Notation, label_to_range, range_to_label, get_block_col.
    • opts: options.
      • opts.lambda: lambda for the Lasso problem.
      • opts.max_iter: maximum iterations of fista algorithm. See also fista, lasso_fista.
      • others.
  • OUTPUT:
    • pred: predicted labels of test samples.
    • X: solution of the lasso problem.

ODL

• An implementation of the well-known Online Dictionary Learning method [2].

• Solving the dictionary learning problem:

  [D, X] = arg min_{D, X} 0.5||Y - DX||_F^2 + lambda||X||_1 subject to ||d_i||_2 <= 1.

• Folder ./ODL.

Supporting funtions:

ODL

• The algorithm to solve the main problem stated above.
• Syntax: [D, X] = ODL(Y, k, lambda, opts, sc_method)
  • INPUT:
    • Y: collection of samples.
    • k: number of bases in the desired dictionary.
    • lambda: norm 1 regularization parameter.
    • opts: option.
    • sc_method: sparse coding method used in the sparse coefficient update. Possible values:
      • 'fista': using FISTA algorithm. See also fista.
      • 'spams': using SPAMS toolbox [12].
  • OUTPUT:
    • D, X: as in the problem.

ODL_cost

• Calculating cost
• Syntax cost = ODL_cost(Y, D, X, lambda)

ODL_updateD

• The dictionary update algorithm in ODL.

• Solving the optimization problem:

  D = arg min_D -2trace(E'*D) + trace(D*F*D') subject to: ||d_i||_2 <= 1, where F is a positive semidefinite matrix.

• Syntax [D, iter] = ODL_updateD(D, E, F, opts)

  • INPUT:
    • D, E, F as in the above problem.
    • opts. options:
      • opts.max_iter: maximum number of iterations.
      • opts.tol: when the difference between D in two successive iterations less than this value, the algorithm will stop.
  • OUTPUT:
    • D: solution.
    • iter: number of run iterations.

LCKSVD

FDDL

FDDL_fidelity

• Syntax: cost = FDDL_fidelity(Y, Y_range, D, D_range, X)
• Calculating the fidelity term in FDDL[4]:
• $\sum_{c=1}^C \Big(|Y_c - D_cX^c_c|F^2 + \sum{i \neq c} |D_c X^c_i|_F^2\Big)$

FDDL_discriminative

• Syntax: cost = FDDL_discriminative(X, Y_range)
• calculating the discriminative term in FDDL[4]:
• $|X|F^2 + \sum{c=1}^C (|Xc - Mc|_F^2 - |Mc - M|_F^2) $

FDDL_cost

• FDDL_cost(Y, Y_range, D, D_range, X, lambda1, lambda2)

FDDL_updateX

FDDL_updateD

FDDL_pred

DLSI

DLSI_term

• Syntax: cost = DLSI_term(D, D_range)
• Calculating the structured incoherence term in DLSI [5].
• $sum_{c=1}^C sum_{i \neq c} ||D_i^TD_c||_F^2$

DLSI_cost

• function cost = DLSI_cost(Y, Y_range, D, D_range, X, opts)
• Calculating cost function of DLSI with parameters lambda and eta are stored in opts.lambda and opts.rho
• f(D, X) = 0.5sum_{c=1}^C 05||Yc - DcXc||_F^2 + lambda||X||1 + 05etasum{i \neq c} ||Di^T*Dc||_F^2

DLSI

• function [D, X, rt] = DLSI(Y, Y_range, opts)
• The main DLSI algorithm
• INPUT:
  • Y, Y_range: training samples and their labels
  • opts:
    • opts.lambda, opts.eta: lambda and eta in the cost function
    • opts.max_iter: maximum iterations.
• OUTPUT:
  • rt: total running time of the training process.
• [D, X, rt] = argmin_{D, X}(\sum 0.5*||Y_c - D_c X_c||_F^2) + \lambda*norm1(X) + 0.5*eta * \sum_{i \neq c} ||D_i^T D_c||_F^2
• updating X: Xi = arg\min 0.5*||Y_c - D_c X_c||_F^2 + \lambda ||X_c||
• updating D: Di = \arg\min ||Y_c - D_c X_c||_F^2 + \eta ||D_{\c}^T D_c||_F^2

DLSI_updateD

• function D = DLSI_updateD(Y, X, D, A, lambda, opts)

• Solving problem: D = \arg\min_D -2trace(ED') + trace(FD'*D) + \lambda *\|A*D\|F^2, subject to: ||d_i||_2^2 \leq 1

• ADMM approach

• rewrite: [D, Z] = arg\min -2trace(ED') + trace(FD'*D) + \lambda ||A*Z||_F^2, subject to D = Z; ||d_i||_2^2 \leq 1 aproach 1: ADMM.

  • D = \arg\min -2trace(ED') + trace(FD'*D) + \rho/2 ||D - Z + U||_F^2, s.t. ||d_i||_2^2 \leq 1
    • Z = \arg\min \lambda*||A*Z|| + \rho/2||D - Z + U||_F^2
  • U = U + D - Z

• solve D: D = \arg\min-2trace(ED') + trace(FD'*D) + \rho/2 ||D - W||_F^2 with W = Z - U; D = \arg\min -2trace((E - \rho/2*W)*D') + trace((F + \rho/2 * eye())*D'D)

• solve Z: derivetaive: 0 = 2A'AZ + \rho (Z - V) with V = D + U Z = B*\rho V with B = (2\lambdaA'*A + \rho I)^{-1}

DLSI_pred

• function pred = DLSI_pred(Y, D, opts)
• predict the label of new input Y given the trained dictionary D and parameters stored in opts

DLSI_top

• function DLSI_top(dataset, N_train, k, lambda, eta)
• The top function of DLSI
• INPUT:
  • dataset: name of the dataset stored in .mat file in data folder. Note that dataset is the file name of the .mat, excluding .mat.
  • N_train: number of training samples in each class
  • k: number of bases in EACH dictionary
  • lambda, eta: regularization parameters.
• To run an small example, type DLSI_top without input in MATLAB command window.

DLCOPAR

DLCOPAR

DLCOPAR_cost

DLCOPAR_updateX

DLCOPAR_updateD

DLCOPAR_top

• function DLCOPAR_top(dataset, N_train, k, k0, lambda, eta)
• The top function of DLCOPAR
• INPUT:
  • dataset: name of the dataset stored in .mat file in data folder. Note that dataset is the file name of the .mat, excluding .mat.
  • N_train: number of training samples in each class
  • k: number of bases in EACH PARTICULAR dictionary
  • k0: number of bases in the COMMON dictionary
  • lambda, eta: regularization parameters.
• To run an small example, type DLCOPAR_top without input in MATLAB command window.

LRSDL

LRSDL_top

• Syntax LRSDL_top(dataset, N_train, k, lambda1, lambda2, lambda3)

FuzzyDL

References

[1]. Wright, John, et al. "Robust face recognition via sparse representation." Pattern Analysis and Machine Intelligence, IEEE Transactions on 31.2 (2009): 210-227. paper

[2]. Mairal, Julien, et al. "Online learning for matrix factorization and sparse coding." The Journal of Machine Learning Research 11 (2010): 19-60. [paper]

[3]. Jiang, Zhuolin, Zhe Lin, and Larry S. Davis. "Label consistent K-SVD: Learning a discriminative dictionary for recognition." Pattern Analysis and Machine Intelligence, IEEE Transactions on 35.11 (2013): 2651-2664. [Project page]

[4]. Yang, Meng, et al. "Fisher discrimination dictionary learning for sparse representation." Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011. [paper], [code]

[5]. Ramirez, Ignacio, Pablo Sprechmann, and Guillermo Sapiro. "Classification and clustering via dictionary learning with structured incoherence and shared features." Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010. [paper]

[6]. Discriminative Feature-Oriented dictionary Learning[^fn_dfdl]. Tiep H. Vu, H. S. Mousavi, V. Monga, A. U. Rao and G. Rao, "Histopathological Image Classification using Discriminative Feature-Oriented dictionary Learning", IEEE Transactions on Medical Imaging , volume 35, issue 3, pages 738-751, March 2016. [paper] [Project page]

[7]. Kong, Shu, and Donghui Wang. "A dictionary learning approach for classification: separating the particularity and the commonality." Computer Vision ECCV 2012. Springer Berlin Heidelberg, 2012. 186-199. [[paper]] (http://www.cs.zju.edu.cn/people/wangdh/papers/draft_ECCV12_particularity.pdf)

[8]. Yang, Meng, et al. "Latent dictionary learning for sparse representation based classification." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014.[paper]

[9]. Tiep H. Vu, Vishal Monga. "Learning a low-rank shared dictionary for object classification." Submitted to International Conference on Image Processing (ICIP) 2016. [paper]

[10]. A singular value thresholding algorithm for matrix completion." SIAM Journal on Optimization 20.4 (2010): 1956-1982. [paper]

[11]. Beck, Amir, and Marc Teboulle. "A fast iterative shrinkage-thresholding algorithm for linear inverse problems." SIAM journal on imaging sciences 2.1 (2009): 183-202. [paper]

[12]. The Sparse Modeling Software