PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Low-rank Shared Dictionary Learning for Image Classification

Tiep Vu, Vishal Monga

arXiv:1610.08606v3cs.CVcs.AI

TL;DR

The paper addresses the challenge of modeling class-specific features alongside patterns shared across object classes. It proposes LRSDL with constrained shared and particular dictionaries, plus faster optimization procedures, and reports lower computational complexity than competing original methods.

  • Problem

    Existing discriminative dictionary-learning methods can overlook shared features, while shared-dictionary approaches may allow the shared subspace to absorb class-specific atoms.

  • Method

    LRSDL jointly learns class-specific dictionaries under FDDL constraints and a shared dictionary constrained by low rank and similar shared codes, with efficient update algorithms.

  • Results

    LRSDL requires less computation than competing original dictionary-learning models, while the proposed efficient algorithms improve computational cost and running time.

  • Takeaways & Limitations

    The framework provides a shared-and-particular dictionary model for classification and extends efficient optimization procedures to related dictionary-learning methods.

Abstract

from arXiv · show

Despite the fact that different objects possess distinct class-specific features, they also usually share common patterns. This observation has been exploited partially in a recently proposed dictionary learning framework by separating the particularity and the commonality (COPAR). Inspired by this, we propose a novel method to explicitly and simultaneously learn a set of common patterns as well as class-specific features for classification with more intuitive constraints. Our dictionary learning framework is hence characterized by both a shared dictionary and particular (class-specific) dictionaries. For the shared dictionary, we enforce a low-rank constraint, i.e. claim that its spanning subspace should have low dimension and the coefficients corresponding to this dictionary should be similar. For the particular dictionaries, we impose on them the well-known constraints stated in the Fisher discrimination dictionary learning (FDDL). Further, we develop new fast and accurate algorithms to solve the subproblems in the learning step, accelerating its convergence. The said algorithms could also be applied to FDDL and its extensions. The efficiencies of these algorithms are theoretically and experimentally verified by comparing their complexities and running time with those of other well-known dictionary learning methods. Experimental results on widely used image datasets establish the advantages of our method over state-of-the-art dictionary learning methods.

I. INTRODUCTION

The paper motivates learning dictionaries that represent both shared and class-specific features, then introduces LRSDL and efficient algorithms for dictionary-learning subproblems. It also analyzes computational complexity and provides implementations for reproducibility.

  • Class-specific dictionary-learning methods often assume non-overlapping class subspaces, although objects from different classes can share features such as scene backgrounds.
  • LRSDL jointly learns class-specific dictionaries and a shared dictionary to extract discriminative and common features for image classification.
  • The shared dictionary is constrained to be low-rank, while its sparse coefficients are encouraged to be similar across signals.
  • The paper develops efficient algorithms for sparse-coefficient and dictionary updates in FDDL, LRSDL, and DLSI, using FISTA, ODL, and ADMM procedures.
  • The work derives complexity analyses, reports experimental running times, and releases MATLAB and Python implementations of several sparse-coding and dictionary-learning methods.

B. Closely related work: Fisher discrimination dictionary learning (FDDL)

The framework extends Fisher discrimination dictionary learning by combining class-specific discriminative modeling with a shared dictionary. Shared atoms represent common structure, while low-rankness and code similarity limit their ability to absorb class-specific information.

  • Fisher discrimination dictionary learning (FDDL): FDDL learns discriminative dictionaries and sparse coefficients using structured fidelity, Fisher-based coefficient constraints, and sparsity regularization.
  • Generativity: The shared dictionary is required to represent samples from all classes together with each class-specific dictionary.
  • Low-rankness: Low-rank regularization prevents the shared dictionary from absorbing discriminative atoms by constraining its spanned subspace to have low dimension.
  • Code similarity: During classification, the shared contribution is removed before class identity is determined, while shared codes are encouraged to remain close to their mean.
  • The proposed objective jointly learns shared and class-specific dictionaries, and reduces to FDDL when the shared dictionary is removed.

D. Efficient solutions for optimization problems

The paper develops efficient alternating updates for FDDL and extends them to LRSDL, replacing costly blockwise procedures with lower-cost optimization steps.

  • Efficient FDDL dictionary update: The original FDDL dictionary update solves C class-specific subproblems sequentially, making it time-consuming and inaccurate.The proposed update instead optimizes the total dictionary while X is fixed.
  • Efficient FDDL dictionary update: E-FDDL-D updates the total dictionary jointly when X is fixed, significantly reducing computational cost.The resulting problem can be solved using Online Dictionary Learning.
  • Efficient FDDL sparse coefficient update: With D fixed, FDDL sparse coefficients are updated by solving the coefficient subproblem using FISTA.The gradient is computed through a lemma for the structured function involving block matrices.
  • LRSDL extensions: The paper extends the efficient FDDL dictionary and coefficient updates to LRSDL because LRSDL is an extension of FDDL.LRSDL updates D and D0 separately when X is fixed.
  • LRSDL extensions: The LRSDL shared dictionary D0 is updated using ADMM together with singular value thresholding.The procedure alternates subproblems after initializing Z and U to D0.

4) LRSDL sparse coefficients update (LRSDL-X):

LRSDL combines the shared and class-specific coefficient updates into one optimization problem and solves the resulting sparse-coding step with FISTA.

  • LRSDL sparse coefficients update: The proposed sparse-coefficient update combines the X and X0 problems into a single optimization problem.This replaces the alternating treatment used in the preliminary work.
  • LRSDL sparse coefficients update: FISTA updates X after calculating the gradient of the objective's two parts.The algorithm extracts X and X0 from an auxiliary iterate during each update cycle.
  • LRSDL sparse coefficients update: Algorithm 1 repeatedly updates the coefficients until convergence or until reaching kmax iterations.The resulting X and X0 are extracted from the auxiliary variable after the iterative procedure.
  • LRSDL sparse coefficients update: The gradient uses block means M = µ(X), Mc = µ(Xc), and their concatenation cM.These quantities support the structured regularization term in the coefficient update.

0 D0X0 −2DT 0 V + λ2(X0 −M0),

The complete LRSDL optimization alternates coefficient updates with separate dictionary updates, using FISTA for coefficients and ODL or ADMM-based procedures for dictionaries.

  • Overall LRSDL algorithm: The Lipschitz coefficient of the gradient is required when applying FISTA to update X.In experiments, an upper bound of the gradient's Lipschitz constant is used.
  • Overall LRSDL algorithm: The overall LRSDL algorithm first updates X and X0 using Algorithm 1, then updates D and D0.Initialization sets X to zero before these alternating steps.

E. Efficient solutions for other dictionary learning methods

The paper also introduces efficient dictionary updates for DLSI and COPAR, centered on reducing repeated matrix inversions, and compares their computational complexity with original methods.

  • Efficient updates for DLSI and COPAR: The paper proposes efficient dictionary-update algorithms for DLSI and COPAR in addition to LRSDL and FDDL.The same update strategy is intended for common and particular dictionaries in COPAR.
  • Efficient DLSI update: E-DLSI-D requires one matrix inversion, whereas the original DLSI update requires one inversion for each of the kc dictionary columns.The efficient procedure uses ADMM to update Dc.
  • Complexity analysis: The complexity analysis estimates each algorithm by the approximate number of multiplications required for one sparse-code and dictionary-update iteration.The comparison includes LRSDL, DLSI, COPAR, and FDDL.
  • Complexity analysis: For ODL-X, the total complexity is k(kd + dn + qkn).This includes precomputing DT D and DT Y plus q FISTA iterations.
  • Complexity analysis: ODL-D has complexity qdk^2 because each of k dictionary columns is updated across q iterations.The dominant computation is evaluating Df_i.

B. Dictionary learning with structured incoherence (DLSI)

DLSI, COPAR, and FDDL use structured class-specific dictionaries, while efficient update procedures reduce computational cost relative to original algorithms. The analysis compares their update complexities and total per-iteration costs.

  • DLSI encourages independence between different classes by minimizing coherence between cross-class bases.
  • Efficient DLSI dictionary updates replace repeated matrix inversions with a lower-cost procedure involving one inversion and matrix multiplications.The original update has complexity Cqkd3, whereas the efficient update is C(q2dk2 + d3 + qd2k).
  • COPAR explicitly uses a shared dictionary but does not impose a low-rank constraint on it.
  • COPAR sparse-code updates have approximate complexity C3k2(2d + Ck + qn) under the stated large-C assumptions.
  • The efficient COPAR dictionary update has approximate complexity C(q2dk2 + d3 + qd2k), compared with roughly Cqkd3 for the original update.
  • FDDL’s original dictionary update solves C class-specific subproblems, with total complexity Cdk(qk + C2n).

E. LRSDL

LRSDL updates class-specific coefficients, class-specific dictionaries, and the shared dictionary within its low-rank shared-dictionary framework. Its class-specific update costs are similar to efficient FDDL, while shared-dictionary updating adds an SVD and matrix multiplications.

  • LRSDL coefficient updating uses computations involving D, Y, D0X0, and block-matrix operations.
  • LRSDL dictionary updating requires one additional computation of Y = Y−D0X0 compared with efficient FDDL.
  • The LRSDL class-specific dictionary-update complexity is similar to that of efficient FDDL.
  • Updating the shared dictionary D0 includes a shrinkage-thresholding operator requiring one SVD and two matrix multiplications.
  • The total LRSDL complexity is obtained by combining the complexities of coefficient updating, class-specific dictionary updating, and shared-dictionary updating.

F. Summary

The paper evaluates LRSDL and competing dictionary-learning methods across diverse image datasets, reporting computational, convergence, and classification results. Efficient variants substantially reduce runtime, while LRSDL maintains strong performance as training data decreases.

  • The complexity comparison uses C = 100, n = 20, k = 10, q = 50, and d = 500 as a representative parameter setting.
  • Under this setting, LRSDL is the least expensive original dictionary-learning method, while only E-FDDL has lower complexity and COPAR is the most expensive.
  • Experiments cover Extended YaleB, AR face, AR gender, Oxford Flower, Caltech 101, and COIL-100, using repeated random splits and five-fold cross-validation.
  • More than 12,000 seconds are required by O-FDDL for 100 iterations, whereas E-FDDL completes the same task in half an hour.

2) E-DLSI-D and E-COPAR-D:

The experiments compare efficient dictionary-learning algorithms, shared-dictionary behavior, classification accuracy, parameter robustness, and runtime. LRSDL generally provides strong accuracy, robustness to shared-dictionary settings, and lower computation than competing models.

  • Efficient algorithms: Efficient DLSI and COPAR algorithms substantially reduce runtime while slightly improving cost-function values.The paper uses the efficient versions for subsequent classification experiments.
  • Visualization of learned shared bases: LRSDL nearly perfectly separates class-specific and shared elements in the toy experiment, whereas COPAR and JDL retain some cross-dictionary mixing.The paper attributes LRSDL’s result to its low-rank shared-dictionary constraint.
  • Effect of shared dictionary size: LRSDL is robust to shared-dictionary size and improves as η increases, while COPAR worsens when its shared dictionary becomes larger.LRSDL remains robust even when the low-rank constraint is removed, owing to its coefficient-similarity constraint.
  • Overall classification accuracy: LRSDL achieves the highest overall classification values in most dataset comparisons among the evaluated methods.Table III reports mean ± standard deviation accuracies across the presented datasets.
  • Training-set dependence: LRSDL shows the most graceful accuracy decline as the training set is reduced across the first five datasets.COIL-100 is excluded because it already has only 10 training images per class.
  • Parameter sensitivity: LRSDL accuracy exceeds 98% for most tested parameter settings on the AR face dataset.The best reported setting is λ1 = 0.01, λ2 = 0.003, and η = 0.003.
  • Runtime comparison: LRSDL training takes around half an hour on Oxford Flower, about 10 times faster than COPAR and faster than D2L2R2 and SRRS.The runtime comparison is consistent with the reported complexity analysis.
  • Discussion and conclusion: The framework combines a low-rank shared dictionary with similar shared coefficients and reports better average classification performance than state-of-the-art methods.The same constraints are associated with robustness to k0 and η.

APPENDIX

The appendix develops block-matrix notation and gradient identities used to analyze dictionary-learning subproblems. These identities express class-block selection and gradients through matrix operators.

  • Block-matrix notation: Binary class-membership vectors define diagonal matrices that select dictionary blocks for each class.Left and right multiplication isolate corresponding block rows and columns.
  • Proof structure: The displayed block identities support the lemmas used in the efficient sparse-coefficient update.Several derivations conclude with proved lemmas.
  • Gradient identities: The appendix separately derives gradients for squared coefficient norms and related auxiliary terms.The derivation includes expressions involving 2X and matrix operators.
  • Gradient identities: The appendix rewrites the data-fitting gradient using M(D^T D)X − M(D^T Y).This identity is presented for the gradient with respect to sparse coefficients.
  • Gradient identities: The coefficient-similarity term has gradients expressed through differences between class-specific coefficient blocks and their aggregate mean.The appendix writes these differences as X − cM and cM − M.

C. Proof of Lemma 3

The supplied appendix passage begins the proof of Lemma 3 under fixed Y, D, and X, then concludes the lemma after an algebraic rewrite.

  • Proof of Lemma 3: Lemma 3 is analyzed with Y, D, and X held fixed.The passage then states that the expression can be rewritten before concluding the proof.
  • Proof of Lemma 3: The proof concludes after the rewritten expression and states that Lemma 3 has been proved.The supplied material does not state the full lemma expression.
Loading 1610.08606v3…