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

Dictionary-learning methods often assume non-overlapping class subspaces, although objects can share features. LRSDL learns low-rank shared and class-specific dictionaries, and the authors report better classification performance with less computation than competing models.

  • Problem

    Many discriminative dictionary-learning methods assume non-overlapping class subspaces, although objects from different classes can share common features.

    Source: A. Closely Related work and Motivation · p. 2

  • Method

    LRSDL jointly learns low-rank shared and class-specific dictionaries, with similar coefficients for the shared dictionary and FDDL constraints for the class-specific dictionaries.

    Source: §V · p. 13

  • Results

    The authors report that LRSDL offers better classification performance and requires less computation than competing dictionary-learning models.

    Source: §V · p. 13

  • Takeaways & Limitations

    The authors report that LRSDL is robust to the shared dictionary's size and regularization parameter.

    Source: §V · p. 13

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 … A. Notation

The paper introduces LRSDL, which learns class-specific and shared features while constraining the shared dictionary to be low-rank and its coefficients to be similar. It also presents efficient solvers for dictionary-learning subproblems and analyzes their computational complexity.

I. INTRODUCTION

  • SRC represents samples sparsely using dictionary bases, ideally producing class-aligned, block-diagonal coefficients; later methods learn discriminative class-specific dictionaries.D-KSVD and LC-KSVD encourage sparse codes to match class labels, while DFDL and FDDL apply Fisher-based ideas; D2L2R2 adds a low-rank constraint to each sub-dictionary to reduce noise effects.Source: §I · p. 1

A. Closely Related work and Motivation

  • Because classes can share features, the non-overlapping-subspace assumption is unrealistic; LRSDL addresses limitations of methods that learn shared dictionaries without these constraints.DLSI leaves shared features hidden in sub-dictionaries, while COPAR, JDL, and CSDL explicitly learn a shared dictionary but may let it span class-specific features.Source: A. Closely Related work and Motivation · p. 2

B. Contributions

  • LRSDL jointly learns class-specific dictionaries and shared features, constraining the shared dictionary to be low-rank and its coefficients to be similar.The framework extends FDDL with the ability to capture shared features; the authors state that both shared-dictionary constraints are important.Source: B. Contributions · p. 2, A. Closely Related work and Motivation · p. 2
  • The paper gives efficient FDDL coefficient and dictionary updates, plus a DLSI dictionary update using one matrix inversion instead of several.The FDDL coefficient update uses FISTA with a new block-matrix function and lemma; its dictionary update uses ODL, and LRSDL benefits from these procedures.Source: B. Contributions · p. 2
  • The authors derive operation-count complexity estimates for multiple dictionary-learning methods and compare efficient algorithms with their original counterparts in complexity and running time.Source: B. Contributions · p. 2
  • The paper provides MATLAB and Python toolbox implementations of SRC, ODL, LC-KSVD, efficient DLSI, COPAR, FDDL, D2L2R2, and LRSDL.Source: B. Contributions · p. 2

II. DISCRIMINATIVE DICTIONARY LEARNING FRAMEWORK — A. Notation

  • The notation defines shared and class-specific dictionaries and their coefficients, data matrices and dimensions, and constrains each dictionary basis to have Euclidean norm at most 1.It also defines coefficient-mean matrices used in the Fisher-based notation.Source: A. Notation · p. 3
  • For block matrices, M(A) doubles diagonal blocks; the notation section also recalls FISTA for convex differentiable objectives with Lipschitz-continuous gradients.FISTA computes the gradient at each iteration, and the paper focuses on calculating that gradient efficiently.Source: A. Notation · p. 3

B. Closely related work: Fisher discrimination dictionary learning (FDDL) … 3) Code similarity:

FDDL learns discriminative dictionaries and coefficients using Fisher-based and sparsity terms. LRSDL adds a shared dictionary constrained for generativity, low rank, and similar shared codes alongside class-specific dictionaries.

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

  • FDDL learns a discriminative dictionary and sparse coefficients using Fisher-based discrimination and a term that limits cross-class representation.Its coefficient objective becomes convex with respect to X when the final ∥X∥2 term is included.Source: B. Closely related work: Fisher… · p. 3

1) Generativity:

  • The shared dictionary should represent samples from all classes in collaboration with their class-specific dictionaries.This generativity condition is necessary but insufficient: an overly large shared dictionary could absorb discriminative features.Source: 1) Generativity · pp. 3–4, 2) Low-rankness · p. 4

2) Low-rankness:

  • LRSDL uses the nuclear norm of the shared dictionary as a convex relaxation of rank to prevent it from absorbing discriminative atoms.The authors note that COPAR and JDL do not impose this low-rank constraint.Source: 2) Low-rankness · p. 4

3) Code similarity:

  • For classification, LRSDL removes the shared-dictionary contribution from a test sample before determining its identity.The shared component is excluded because it is not expected to contain class-specific features.Source: 3) Code similarity · p. 4
  • LRSDL encourages each shared code x0 to remain close to the mean shared code m0, preventing class-specific contributions from appearing in shared codes.A low-rank shared dictionary alone may still contribute differently to each class.Source: 3) Code similarity · p. 4

C. Proposed Low-rank shared dictionary learning (LRSDL)

D. Efficient solutions for optimization problems … 3) LRSDL dictionary update (LRSDL-D):

The optimization section first develops efficient updates for FDDL, then extends those algorithms to LRSDL, updating its class-specific and shared dictionaries separately. The updates use ODL, FISTA, and ADMM with singular value thresholding.

D. Efficient solutions for optimization problems

1) Efficient FDDL dictionary update:

  • E-FDDL-D jointly optimizes the total dictionary with coefficients fixed, avoiding O-FDDL-D’s repeated class-specific updates, which are described as time-consuming and inaccurate.The original approach updates one class-specific dictionary at a time while holding the others fixed, repeating until convergence.Source: 1) Efficient FDDL dictionary update · pp. 4–5
  • With coefficients fixed, E-FDDL-D uses a lemma to express the dictionary problem equivalently, and the resulting problem can be solved by ODL.The update concerns the total dictionary D.Source: 1) Efficient FDDL dictionary update · p. 5

2) Efficient FDDL sparse coefficient update (E-FDDL-X):

  • With D fixed, E-FDDL-X casts the coefficient update in a form solvable by FISTA and provides gradients for its optimization.The passages give gradients for the objective components with respect to X.Source: 2) Efficient FDDL sparse coefficient… · p. 5

3) LRSDL dictionary update (LRSDL-D):

  • For LRSDL, the dictionary update separates D and D0; D is updated using E-FDDL-D with the residualized data Y − D0X0.The paper states f_Y(D, X) = f_Ŷ(D, X), where Ŷ ≜ Y − D0X0.Source: 3) LRSDL dictionary update (LRSDL-D) · p. 5
  • For fixed D and X, LRSDL updates D0 using ADMM and singular value thresholding, with one subproblem solvable by ODL and two others described as inexpensive.The ADMM procedure alternates among subproblems until convergence.Source: 3) LRSDL dictionary update (LRSDL-D) · p. 5

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

LRSDL-X combines the updates for X and X0 into one optimization for X, solved using FISTA. The section also outlines how this update fits into the overall LRSDL algorithm.

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

  • LRSDL-X combines the problems of updating X and X0 into one optimization for X, which is updated with FISTA [34], rather than the preliminary alternating approach.The update uses the gradient of h(X).Source: 4) LRSDL sparse coefficients update… · pp. 5–6
  • The gradient combines upper and lower terms to calculate the two-part gradient used in the coefficient update.The passages identify an upper term, a lower term, and their combination, but do not provide enough equation content to specify their formulas.Source: 4) LRSDL sparse coefficients update… · pp. 5–6
  • The overall LRSDL algorithm initializes X to zero, updates X and X0 via Algorithm 1, and updates dictionaries using ODL and ADMM.The algorithm description also notes that the FISTA update requires a Lipschitz coefficient for the gradient.Source: 4) LRSDL sparse coefficients update… · p. 6, §4 · p. 6

4. Update D0 · E. Efficient solutions for other dictionary learning methods

The section proposes an ADMM-based dictionary update for DLSI that reduces matrix inversions, and notes its use for both common and particular dictionary updates in COPAR.

E. Efficient solutions for other dictionary learning methods

  • The paper proposes efficient dictionary-update algorithms for two established methods, DLSI and COPAR.For COPAR, the algorithm is applicable to the common-dictionary and particular-dictionary update subproblems.Source: E. Efficient solutions for other… · pp. 6–7
  • The original DLSI dictionary update inverts a matrix separately for each of the k_c columns, making it computationally costly.The proposed method is called E-DLSI-D; the original procedure is referred to as O-FDDL-D in the passage.Source: E. Efficient solutions for other… · p. 6
  • The method formulates the DLSI update using E = Y_c(X_c)^T and F = X_c(X_c)^T, then solves the resulting problem with ADMM.It initializes Z = U = D_c and alternates among subproblems until convergence.Source: E. Efficient solutions for other… · pp. 6–7
  • The proposed ADMM update for DLSI requires only one matrix inversion, and can also update COPAR’s common and particular dictionaries.The paper says it later compares E-DLSI-D with O-DLSI-D theoretically and experimentally, but provides no comparison values here.Source: E. Efficient solutions for other… · p. 7

III. COMPLEXITY ANALYSIS … B. Dictionary learning with structured incoherence (DLSI)

The complexity analysis estimates iterative algorithms by approximate multiplication counts and compares LRSDL with DLSI, COPAR, and FDDL. For ODL, it derives costs for updating sparse codes and the dictionary; DLSI is introduced as promoting independence between classes’ dictionary bases.

III. COMPLEXITY ANALYSIS

  • The comparison estimates approximate multiplications per iteration for LRSDL, DLSI, COPAR, and FDDL, assuming n_c = n, k_i = k, k ≈ n ≪ d, and q iterations to convergence.For consistency, the analysis denotes training samples by Y and sparse codes by X.Source: §III · p. 7

A. Online Dictionary Learning (ODL)

  • ODL is presented through a cost function and an alternating framework with two subproblems, solving for one variable while fixing the others.The variables are training samples Y ∈ R^(d×n), dictionary D ∈ R^(d×k), and sparse codes X ∈ R^(k×n).Source: A. Online Dictionary Learning (ODL) · p. 7

1) Update X (ODL-X):

  • ODL-X costs k^2d + kdn + qk^2n = k(kd + dn + qkn), including precomputed D^T D and D^T Y and q code-update iterations.The per-iteration dominant computation is (D^T D)X.Source: 1) Update X (ODL-X) · p. 7

2) Update D

  • The ODL dictionary update costs qdk^2 multiplications; its dominant operation computes Df_i while updating each of k columns over q iterations.Each column is updated subject to ||d_i||_2 ≤ 1, with E = YX^T and F = XX^T.Source: 2) Update D · p. 7

B. Dictionary learning with structured incoherence (DLSI)

1) Update X (DLSI-X): … 1) Original update X (O-FDDL-X):

This block gives complexity expressions for DLSI and COPAR update variants and reports the original FDDL coefficient-update complexity. It also describes COPAR as a shared-dictionary method without a low-rank constraint.

1) Update X (DLSI-X):

  • Each iteration solves C DLSI-X subproblems, with total complexity Ck(kd + dn + qkn).The passage specifies Yc ∈ R^{d×n}, Dc ∈ R^{d×k}, and Xc ∈ R^{k×n}.Source: 1) Update X (DLSI-X) · p. 7

2) Original update D (O-DLSI-D):

  • O-DLSI-D has complexity Cqkd^3, dominated by matrix inversion for each of C sub-dictionaries over q iterations.The passage says matrix-vector multiplication and vector normalization can be ignored in this estimate.Source: 2) Original update D (O-DLSI-D) · p. 7

3) Efficient update D (E-DLSI-D):

  • E-DLSI-D has complexity C(q^2dk^2 + d^3 + qd^2k) = Cd^3 + Cqdk(qk + d).Its dominant steps include q iterations of ODL-D and one matrix inversion plus q matrix multiplications; steps (33) and (35) require much less computation than (32) and (34).Source: 3) Efficient update D (E-DLSI-D) · pp. 7–8

C. Separating

  • The comparison turns to particularity-and-commonality dictionary learning (COPAR).Source: C. Separating · p. 8

1) Cost function:

  • COPAR uses a shared dictionary without a low-rank constraint, and its cost function is rewritten using LRSDL notation.Source: 1) Cost function · p. 8

2) Update X (COPAR-X):

  • Under C ≫ 1, q ≫ 1, n ≈ k ≪ d, COPAR-X has approximate complexity C^3k^2(2d + Ck + qn).The update solves each Xc via an l1-norm regularization problem; the rewritten dimensions are d̃ = 2d + (C − 1)k and k̃ = (C + 1)k.Source: 2) Update X (COPAR-X) · p. 8

3) Update D (COPAR-D):

  • For large C, O-COPAR-D has approximate complexity Cqkd^3, while E-COPAR-D has C(q^2dk^2 + d^3 + qd^2k).The total complexities of O-COPAR and E-COPAR are summarized in Table II, and the estimate assumes C + 1 ≈ C.Source: 3) Update D (COPAR-D) · p. 8

1) Original update X (O-FDDL-X):

2) Efficient update X (E-FDDL-X): … 1) Update X, X0:

The section analyzes computational costs for efficient FDDL updates and LRSDL updates. It reports that LRSDL’s X and D updates have complexity similar to their E-FDDL counterparts under the stated condition for X.

2) Efficient update X (E-FDDL-X):

3) Original update D (O-FDDL-D):

  • O-FDDL-D divides dictionary updating into C subproblems, solving one dictionary Dc at a time with the others fixed; its complexity is Cdk(qk + C2n).Source: 3) Original update D (O-FDDL-D) · p. 8

4) Efficient update D (E-FDDL-D):

1) Update X, X0:

  • LRSDL-X has complexity similar to E-FDDL-X when the number of classes C is assumed to be much greater than 1.The analysis derives the cost from the computations needed in each X-update iteration.Source: 1) Update X, X0 · p. 9
  • LRSDL-D requires one additional computation, Y = Y−D0X0, compared with E-FDDL-D, while its overall complexity remains similar.The additional computation is performed as part of the LRSDL dictionary update.Source: 1) Update X, X0 · p. 9
  • LRSDL-D0 uses a shrinkage thresholding operator requiring one SVD and two matrix multiplications, and the total LRSDL complexity is specified in Table II.Source: 1) Update X, X0 · p. 9

F. Summary … B. Validation of efficient algorithms

The experiments compare LRSDL and other dictionary-learning methods across diverse image datasets, report lower complexity for the proposed efficient algorithms, and test their convergence against original versions.

F. Summary

  • LRSDL is least computationally expensive among the original dictionary-learning methods; only E-FDDL has lower complexity, while COPAR is most expensive.Table II compares methods under a typical setting of 100 classes, 20 training samples per class, 10 atoms per sub-dictionary and shared dictionary, dimension 500, and 50 iterations for iterative methods.Source: Table II · p. 9, F. Summary · p. 9
  • All three proposed efficient algorithms require less computation than their original versions, with the greatest speedup for DLSI-D.The comparison assumes C = 100, n = 20, k = 10, q = 50, d = 500, and 50 iterations for each iterative method; q2 = 50 in (49).Source: F. Summary · p. 9

A. Comparing methods and datasets

  • Experiments compare methods on Extended YaleB, AR face, AR gender, Oxford Flower, Caltech 101, and COIL-100, averaging results over 10 random train-test splits.Comparators include SRC, LC-KSVD, DLSI, FDDL, COPAR, D2L2R2, DLRD, JDL, and SRRS; regularization parameters use five-fold cross-validation.Source: A. Comparing methods and datasets · pp. 9–10
  • Face features are random projections of images (d = 504 for Extended YaleB and d = 540 for AR); AR gender uses 300-dimensional PCA features from a balanced 50-male, 50-female subset.For AR gender, training uses the first 25 males and 25 females, while testing uses the remaining 25 of each; Oxford Flower uses Frequent Local Histogram features of dimension 10,000, with 60 training and 20 test images per species.Source: A. Comparing methods and datasets · p. 10
  • Caltech 101 uses 21,504-dimensional ScSPM features reduced by PCA to d = 3000, while COIL-100 uses normalized 1024-dimensional grayscale image vectors and 10 training views per object.Caltech features derive from dense SIFT descriptors and max pooling over 1×1, 2×2, and 4×4 grids; COIL-100 test data comprise the remaining views.Source: A. Comparing methods and datasets · p. 10

B. Validation of efficient algorithms

  • On AR face training samples, the efficient algorithms and their original versions are evaluated for convergence; the reported comparisons cover FDDL, DLSI, and COPAR.The setup uses C = 100 classes, random-face feature dimension d = 300, n = 7 training samples per class, and kc = 7 atoms per particular dictionary.Source: B. Validation of efficient algorithms · p. 10, Figure 5 · p. 10, Figure 6 · p. 10

1) E-FDDL-D and E-FDDL-X: … V. DISCUSSION AND CONCLUSION

The paper evaluates efficient dictionary-learning algorithms and LRSDL, which combines a low-rank shared dictionary with similar shared coefficients. Results cover benchmark accuracy, robustness, runtime, and the limitation that the model shares features across every class.

1) E-FDDL-D and E-FDDL-X:; 2) E-DLSI-D and E-COPAR-D:

C. Visualization of learned shared bases

  • On simulated data, LRSDL nearly perfectly separates shared and class-specific bases, whereas DLSI, LC-KSVD, and FDDL leave shared features in class-specific bases and COPAR and JDL mix the feature types.The paper attributes LRSDL’s separation and perfect results on this data to the low-rank constraint on its shared dictionary.Source: Figure 8 · p. 11, C. Visualization of learned shared bases · pp. 11–12

D. Effect of the shared dictionary sizes on overall accuracy

  • COPAR’s accuracy worsens as the shared dictionary grows, while LRSDL remains robust even without its low-rank constraint and improves as that constraint is strengthened; JDL is robust but less accurate than LRSDL.LRSDL’s similar-coefficient constraint helps prevent class-specific features from being absorbed into the shared dictionary.Source: Figure 9 · p. 11, D. Effect of the shared dictionary… · p. 12

G. Performance of LRSDL with varied parameters

E. Overall Classification Accuracy

  • LRSDL achieves the highest reported accuracy values in most cases, while shared-feature methods generally outperform other dictionary-learning methods across the five datasets.The comparison reports overall accuracy as mean ± standard deviation; the supplied passages do not give the table’s individual values.Source: Table III · p. 12, E. Overall Classification Accuracy · p. 12

F. Performance vs. size of training set

H. Run time of different dictionary learning methods

V. DISCUSSION AND CONCLUSION

  • LRSDL combines a low-rank shared dictionary and similar shared coefficients, but its model assumes each shared feature belongs to every class; future work will investigate hierarchical models for features common to subsets of classes.The paper also reports that LRSDL offers better average classification performance than state-of-the-art algorithms developed for these tasks.Source: §V · p. 13

APPENDIX · A. Proof of Lemma 1 · B. Proof of Lemma 2

The appendix proves Lemma 1 through block-selection operations and proves Lemma 2 by deriving gradients for f and g.

A. Proof of Lemma 1

  • For Lemma 1, Wc is a diagonal mask selecting columns of D that belong to class c.Its binary vector wc has entry one exactly for columns belonging to Dc.Source: A. Proof of Lemma 1 · p. 13
  • The text states i = DWcXi, rewrites fY,X(D), and then introduces definitions displaying entries A11, A1j, A1C, A21, Ajj, A2C, AC1, ACj, and ACC.Source: A. Proof of Lemma 1 · p. 13
  • Left-multiplying by Wj isolates the j-th block row, while right-multiplying by its transpose isolates the j-th block column.Combining these operations yields the block-selection result used to prove Lemma 1.Source: A. Proof of Lemma 1 · pp. 13–14

B. Proof of Lemma 2

  • For Lemma 2, the proof gives the gradient identity ∂(2fY,D(X))/∂X = M(D^T D)X − M(D^T Y).The proof first frames the gradient derivation as one of two parts.Source: B. Proof of Lemma 2 · p. 14
  • For the gradient of g, the proof writes the centered matrix difference as X − cM, where cM is formed from the class matrices M1,…,MC.This identity is labeled equation (50) in the passage.Source: B. Proof of Lemma 2 · p. 14
  • The proof expresses Mc − M as cM − M before deriving the gradient of g.The two expressions are stated as equivalent in the proof.Source: B. Proof of Lemma 2 · p. 14
  • The proof states that differentiating 2g(X) with respect to X yields the resulting gradient, ∂(2g(X))/∂X = 2X + M − 2cM.Source: B. Proof of Lemma 2 · p. 14

C. Proof of Lemma 3

With Y, D, and X fixed, the proof rewrites (54) and concludes that Lemma 3 is proved.

C. Proof of Lemma 3

Related papers

Loading 1610.08606v3…