PaperlayerView exact revision on arXiv

Source-linked AI summary

Convolutional Dictionary Learning: A Comparative Review and New Algorithms

Cristina Garcia-Cardona, Brendt Wohlberg

arXiv:1709.02893v5cs.LGeess.IVstat.ML

TL;DR

Convolutional dictionary learning lacks clear evidence about which algorithms are most effective because dictionary updates are computationally challenging and prior comparisons are incomplete. This paper conducts thorough comparisons and proposes new methods, finding that the leading algorithms depend on whether processing is serial or parallel and whether spatial masking is used.

  • Problem

    Incomplete comparisons and computationally expensive dictionary updates leave the most effective convolutional dictionary learning algorithms unclear.

  • Method

    The paper thoroughly compares existing methods and proposes new dictionary-learning approaches for masked and mask-free settings.

  • Results

    In serial processing, the proposed FISTA update performs best, whereas parallel consensus is fastest without masking and hybrid consensus is fastest with masking.

  • Takeaways & Limitations

    The comparisons identify leading convolutional dictionary learning algorithms according to processing mode and the presence of a spatial mask.

Abstract

from arXiv · show

Convolutional sparse representations are a form of sparse representation with a dictionary that has a structure that is equivalent to convolution with a set of linear filters. While effective algorithms have recently been developed for the convolutional sparse coding problem, the corresponding dictionary learning problem is substantially more challenging. Furthermore, although a number of different approaches have been proposed, the absence of thorough comparisons between them makes it difficult to determine which of them represents the current state of the art. The present work both addresses this deficiency and proposes some new approaches that outperform existing ones in certain contexts. A thorough set of performance comparisons indicates a very wide range of performance differences among the existing and proposed methods, and clearly identifies those that are the most effective.

I. INTRODUCTION · II. CONVOLUTIONAL DICTIONARY LEARNING · A. Sparse Coding

The paper reviews convolutional sparse representations and dictionary learning, addressing the difficulty of identifying state-of-the-art CDL methods through comprehensive comparisons and new algorithms. It also formulates convolutional sparse coding and describes an efficient ADMM solution exploiting frequency-domain structure.

  • I. INTRODUCTION: Convolutional sparse representations use linear filters and coefficient maps to reconstruct entire images, replacing an unstructured dictionary with convolutional structure.This formulation originated as translation-invariant sparse representations and later regained interest through deconvolutional networks and efficient CSC methods.
  • I. INTRODUCTION · II. CONVOLUTIONAL DICTIONARY LEARNING: CDL is harder than CSC because its algorithms alternate between sparse coding and dictionary updates in a problem that is non-convex jointly but convex in either variable separately.The filter-norm constraint prevents scaling ambiguity between filters and coefficients.
  • I. INTRODUCTION: The lack of thorough performance comparisons and systematic parameter studies previously made it difficult to determine which CDL methods represented the state of the art.The paper focuses on subsequent batch-mode methods, whose computationally expensive subproblems commonly use augmented-Lagrangian methods and frequency-domain solutions.
  • I. INTRODUCTION: The paper compares methods from,,, and, shows that two algorithms belong to the same class, and introduces new masked and unmasked CDL approaches.The new unmasked method outperforms existing methods serially, while the masked methods outperform existing methods in serial and parallel contexts.
  • I. INTRODUCTION: The paper also examines parameter sensitivity and proposes simple heuristics for selecting parameters that provide good performance.This contribution addresses the parameter-selection gap identified in prior CDL studies.
  • A. Sparse Coding: Convolutional sparse coding is posed as Convolutional BPDN, with a multiple-image MMV formulation using coefficient maps for each filter and training image.The resulting block-structured matrices allow the problem to be written in standard BPDN MMV form.
  • A. Sparse Coding: ADMM is the most effective current solution for CBPDN, using variable splitting so the auxiliary variable equals the primary variable.Its updates include soft-thresholding, simple arithmetic, and a closed-form step; the penalty parameter ρ strongly affects convergence rate.
  • A. Sparse Coding: The computationally expensive ADMM linear system becomes efficient in the DFT domain, where it decomposes into NK independent systems solvable with the Sherman-Morrison formula.This exploits the concatenated diagonal structure of the transformed convolutional dictionary.

B. Dictionary Update

The dictionary update is formulated as a convolutional MOD problem with filter normalization and finite-support constraints, solved spatially while critical subproblems are handled in the frequency domain. Unlike sparse coding, its frequency-domain linear system has rank-K components, preventing direct use of the Sherman–Morrison solution and making the update more computationally expensive.

  • Formulation: The dictionary update is a convolutional form of Method of Optimal Directions with a constraint on filter normalization.Algorithms are developed in the spatial domain, while critical subproblems are solved in the frequency domain.
  • Constraints: The constraint set enforces both the desired filter support and unit ℓ2 normalization.The support constraint zeros filter regions outside the desired support, combined with ∥x∥2 = 1 in CPN.
  • Computational structure: Most dictionary-update methods require solving a linear system containing the data-fidelity term (1/2) ∥Xd −s∥2.This linear system can be solved in the frequency domain, as in the CSC X step.
  • Computational structure: Rank-K components in X̂H X prevent direct use of the efficient Sherman–Morrison solution, making dictionary updating inherently more computationally expensive than sparse coding.This difference complicates algorithm design and motivates the methods discussed in Sec. III.

C. Update Coupling … 3) Spatial Tiling:

The paper emphasizes that ADMM subproblem coupling depends on iteration frequency and variable selection, with auxiliary-variable coupling generally more stable and faster. For dictionary updates, it examines ADMM-based linear-system solvers including Conjugate Gradient, iterated Sherman–Morrison, and spatial tiling.

  • C. Update Coupling: ADMM coupling is governed by how many iterations each subproblem performs and which working variable passes between subproblems.These are identified as the major design choices in alternating optimization.
  • C. Update Coupling: Most ADMM-based approaches couple sparse coding and dictionary updates through their primary variables.The primary variables correspond, for example, to X in Eq. (12).
  • C. Update Coupling: Primary-variable coupling tends to be unstable, requiring multiple iterations or very large penalty parameters that can slow convergence.The passage presents both multiple inner iterations and large penalties as responses to instability.
  • C. Update Coupling: Auxiliary-variable coupling tends to be more stable, permits alternation without multiple iterations, and converges faster.The auxiliary variables correspond, for example, to Y in Eq. (12).
  • III. DICTIONARY UPDATE ALGORITHMS: Because the best CSC algorithm is not seriously disputed, the work focuses on selecting the dictionary update algorithm.This establishes the methodological focus of the dictionary-update sections.
  • A. ADMM with Equality Constraint: The simplest ADMM approach to Eq. (28) uses variable splitting with an equality constraint.The supplied passage introduces this approach but does not provide the omitted splitting equations.
  • 1) Conjugate Gradient:: Conjugate Gradient solves the DFT-domain linear system iteratively, and a relative residual tolerance of 10−3 or better is sufficient for reliable convergence.Using the previous outer iteration’s solution as the initial value can substantially reduce CG iterations.
  • 2) Iterated Sherman-Morrison:: Iterated Sherman–Morrison is effective for small to moderate K but performs poorly for large K because its computational cost is O(K2).When K = 1, Sherman–Morrison gives a very efficient solution; spatial tiling can transform larger training-image sets into a problem with K′ = 1.

B. Consensus Framework · C. 3D / Frequency Domain Consensus

The consensus formulation recasts the dictionary update as an ADMM problem whose block-diagonal structure yields independent training-image subproblems. The related “3D” method is equivalent to frequency-domain ADMM consensus, with block-circulant convolution and DFT diagonalization linking the two approaches.

  • B. Consensus Framework: The dictionary update is posed as an ADMM consensus problem using block-matrix and vector notation for coefficient maps and dictionary copies.Each d_m,k denotes a distinct copy of dictionary filter m for training image k.
  • B. Consensus Framework: The corresponding optimization procedure is specified through standard ADMM iterations.
  • B. Consensus Framework: Because X is block diagonal, the main ADMM update decomposes into K independent problems.Each independent problem uses the same efficient DFT-domain Sherman–Morrison method as Eq. (13).
  • C. 3D / Frequency Domain Consensus: The “3D” method maps the K > 1 dictionary update to an equivalent K′ = 1 problem by treating K 2D training images as one 3D training volume.Its inherently 3D dictionary filters are constrained to be zero outside the first 3D slice.
  • C. 3D / Frequency Domain Consensus: The “3D” method is ADMM consensus with the data-fidelity term and constraint expressed in the DFT domain.The relationship is illustrated for K = 2 and generalizes to arbitrary K.
  • C. 3D / Frequency Domain Consensus: The equivalent “3D” formulation uses a block-circulant matrix constructed from the blocks X_k, whose multiplication represents convolution in an additional dimension.
  • C. 3D / Frequency Domain Consensus: Applying an un-normalized 2 × 2 block DFT in the extra dimension transforms the objective and constraint into a frequency-domain formulation.
  • C. 3D / Frequency Domain Consensus: Since the DFT diagonalises a circulant matrix, the transformed problem takes the form of an ADMM consensus problem in transformed variables.

D. FISTA · IV. MASKED CONVOLUTIONAL DICTIONARY LEARNING · A. Sparse Coding

The paper introduces FISTA for batch dictionary updates and extends convolutional dictionary learning to masked data, presenting two sparse-coding methods with similar performance but different implementation constraints.

  • D. FISTA: FISTA, an accelerated proximal-gradient method, is applied to the dictionary update of a batch-mode convolutional dictionary-learning algorithm.It had previously been used for convolutional sparse coding and a recent online dictionary-learning algorithm, but not for batch dictionary updates.
  • D. FISTA: The FISTA iterations use t0 = 1 and a parameter L controlling the gradient-descent step size.Although L can be selected by backtracking, the reported experiments use a constant L.
  • D. FISTA: The data-fidelity gradient is computed in the DFT domain, and the updated y(i+1) variable becomes the dictionary update.This follows the frequency-domain treatment advocated for FISTA-based convolutional sparse coding.
  • IV. MASKED CONVOLUTIONAL DICTIONARY LEARNING: A spatial mask W is introduced to learn dictionaries from data with missing samples or reduce boundary artifacts caused by circular DFT convolution conditions.The mask is represented by a diagonal matrix.
  • IV. MASKED CONVOLUTIONAL DICTIONARY LEARNING: Masked convolutional dictionary learning separately minimizes the objective with respect to coefficient maps for sparse coding and filters for dictionary updating.This decomposition mirrors the corresponding unmasked formulation.
  • A. Sparse Coding: Two methods solve the masked MMV CBPDN sparse-coding problem: mask decoupling with ADMM or an appended impulse filter with constrained coefficients.The fixed-mask notation can be extended to a distinct Wk for each column, while the impulse-filter approach is restricted to masks with only zero entries in the relevant unconstrained locations.
  • A. Sparse Coding: Both masked sparse-coding approaches provide very similar performance, but mask decoupling is more complicated to implement than the impulse-filter method.The impulse-filter method constrains its coefficient map to zero where the mask is unity and leaves it unconstrained where the mask is zero.

B. Dictionary Update … B. Extended Consensus Framework

The paper develops several ADMM-based strategies for dictionary updates, including block-constraint splitting and a hybrid mask-decoupling/consensus framework. These methods reuse earlier ADMM structures while modifying constraint handling and computational steps for masked updates.

  • B. Dictionary Update: Dictionary updating is formulated as an optimization problem whose solution motivates the algorithms developed in the following sections.The supplied passage introduces the dictionary-update problem but does not include its explicit equation or objective.
  • A. Block-Constraint ADMM: The block constraint can be written in an alternative form to support the block-constraint ADMM formulation.The supplied passage gives an alternative constraint representation, but its mathematical symbols are partially corrupted.
  • A. Block-Constraint ADMM: The block-constraint problem matches Eq. (60) structurally, replacing the ℓ1 norm with the constraint-set indicator function.This substitution preserves most ADMM iterations while changing the proximal or constraint-handling step.
  • V. MASKED DICTIONARY UPDATE ALGORITHMS: The masked dictionary update is addressed through dedicated algorithms within the masked dictionary update section.The extended-consensus passage explicitly refers to the masked dictionary update Eq. (68).
  • B. Extended Consensus Framework: The masked dictionary update can also be solved by combining mask decoupling with ADMM consensus.This hybrid is formulated using the variant notation introduced in Sec. III-B.
  • B. Extended Consensus Framework: The extended-consensus formulation expands the constraints over block components of d, g1, and s.The passages present both a compact constraint form and an expanded block-component representation.
  • B. Extended Consensus Framework: The corresponding ADMM iterations reuse earlier update forms, with Eqs. (74), (75), and (77) matching Sec. III-B steps and Eqs. (76) and (78) matching Sec. V-A steps.The passage explicitly identifies which earlier ADMM steps provide the solution methods for the extended-consensus iterations.

C. FISTA … B. Dictionary Update

The paper extends convolutional dictionary learning to multi-channel data and separately develops sparse-coding and dictionary-update procedures. FISTA handles masked gradients through spatial–frequency-domain transformations, while both multi-channel updates remain computationally comparable to their single-channel counterparts.

  • C. FISTA: FISTA computes convolution operations efficiently in the frequency domain and masking operations in the spatial domain.This transformation addresses the complication introduced by the spatial mask in the gradient calculation.
  • VI. MULTI-CHANNEL CDL: The paper distinguishes single-channel dictionaries with channel-specific coefficient maps from multi-channel dictionaries with shared coefficient maps.It focuses on the latter multi-channel representation; mixtures partitioning channels into subsets are not considered further.
  • VI. MULTI-CHANNEL CDL: Multi-channel CDL represents each dictionary filter and training signal with C channels and alternates sparse-coding and dictionary updates.The variables dc,m and sc,k denote channel-specific components of dictionary filters and training signals, respectively.
  • A. Sparse Coding: The multi-channel sparse-coding problem has the same form as the single-channel MMV problem, with ADMM iterations unchanged except for a C × M block structure.Its frequency-domain matrix can be decomposed into N components of rank C.
  • A. Sparse Coding: The multi-channel sparse-coding objective is not significantly more challenging than the single-channel case because it adds only a sum over the C channels.For images with only three channels, other methods may be suitable, whereas ADMM consensus or FISTA is preferred for significantly more channels.
  • B. Dictionary Update: The multi-channel dictionary update has the same structure as the single-channel case, and the solutions for different channel dictionaries dc are independent.Consequently, the multi-channel dictionary update is no more computationally challenging than the single-channel case.

C. Relationship between K and C … C. Experiments

The paper relates the computational roles of K and C, then compares CDL methods through standardized algorithmic implementations, complexity analysis, and experiments on nested image datasets. The evaluation emphasizes parallel consensus variants and identifies practical convergence and scalability tradeoffs.

  • C. Relationship between K and C: K and C play dual computational roles: C controls the expensive CSC subproblem rank, while K controls the main dictionary-update subproblem rank.
  • VII. RESULTS: The study compares computational performance using optimally selected parameters for each approach to ensure a fair comparison.
  • A. Dictionary Learning Algorithms: The comparison embeds prior dictionary-update contributions within an effective CDL structure using auxiliary-variable coupling and one iteration per subproblem.
  • A. Dictionary Learning Algorithms: Cns-P and M-Cns-P parallelize sparse coding and dictionary-update stages, with synchronization limited to consensus-variable updates.
  • A. Dictionary Learning Algorithms: SA-ADMM had promising computational cost per iteration but noncompetitive convergence, while some faster prior methods were excluded from the main experiments because practical implementations were unavailable.
  • B. Computational Complexity: All methods scale linearly with filters M and images K, except ISM variants, which scale as O(K^2).
  • C. Experiments: Training used nested sets of 5, 10, 20, and 40 greyscale 256 × 256 images, plus an additional 20-image test set for generalization.

D. Optimal Penalty Parameters … G. Penalty Parameter Selection

The paper uses grid searches to establish fair method-specific penalty parameters, compares dictionary-learning methods across training sizes and masked settings, evaluates generalization on held-out images, and motivates heuristic parameter selection. Parallel consensus and FISTA are especially competitive in computation time, while training performance predicts test performance.

  • D. Optimal Penalty Parameters: Grid searches select method-specific penalty parameters by minimizing the CDL functional after prescribed ADMM or FISTA iterations.The searches cover (ρ, σ) for ADMM updates and (ρ, L) for FISTA updates, followed by finer searches around the best coarse-grid center.
  • E. Performance Comparisons: For K = 5, all methods show similar functional-value convergence across iterations, whereas larger training sets favor CG and ISM somewhat in iteration counts.CG has substantially better time scaling depending on the relative residual tolerance, while ISM performs poorly with respect to time.
  • E. Performance Comparisons: The 3D method behaves like ADMM consensus but uses more memory, while spatial tiling converges more slowly in both iterations and time.Neither method is explored further because it provides no substantial advantage over the alternatives.
  • E. Performance Comparisons: Parallel consensus and regular consensus have identical functional evolution over iterations, but parallel consensus requires much less computation time and is fastest overall.Parallel consensus is almost ideally parallelizable, with linear scaling for K ∈[10, 40].
  • E. Performance Comparisons: For masked problems, M-FISTA has mixed iteration convergence but consistently good time convergence, while M-Cns-P is fastest for K = 5 and K = 20.M-FISTA is best by iterations for K = 40, and M-Cns-P slightly lags behind it there.
  • E. Performance Comparisons: Compared with mask-free variants, M-CG and M-ISM perform worse in both time and iterations.The masked CG version may require a relative residual tolerance below 10−3, at the cost of substantially longer computation times.
  • F. Evaluation on the Test Set: On a held-out 20-image test set, dictionaries trained with 40 images outperform those trained with 20 images, independently of method.Training performance generally predicts testing performance, making the functional value on a sufficiently large training set a reliable indicator of dictionary quality.
  • G. Penalty Parameter Selection: Because grid searches are fair but inconvenient for general parameter selection, the paper constructs heuristics for reliably selecting parameters for the best-performing CDL methods.The heuristic approach is presented as an alternative to exhaustive grid searches.

1) Parameter Scaling Properties: … SIII. ANALYTIC DERIVATION OF PENALTY PARAMETER

The paper derives how CDL penalty parameters scale with training-set size, develops empirical selection guidelines, and compares leading serial and parallel algorithms. Supplementary analyses support these results through grid searches and analytic derivations, while noting conditions and limitations on parameter-transferability.

  • 1) Parameter Scaling Properties:: For mask-free CDL, the sparse-coding penalty ρ scales as O(1), while dictionary-update penalty scalings are derived for ADMM and FISTA methods.These estimates cover ADMM with equality constraints, ADMM consensus, and FISTA dictionary updates.
  • 1) Parameter Scaling Properties:: For masked CDL, the sparse-coding penalty ρ and extended-consensus dictionary penalty σ both scale as O(1), whereas block-constraint ADMM has no simple σ-scaling rule.The masked derivations address sparse coding, block-constraint ADMM, and extended ADMM consensus.
  • 2) Parameter Selection Guidelines:: Optimal parameters are expected to be constant or linear in K, and guidelines for CG, Cns, FISTA, and M-Cns were estimated using additional computational experiments.Serial counterparts determine the parameter dependence of Cns-P and M-Cns-P, so those methods were not evaluated separately.
  • 2) Parameter Selection Guidelines:: Parameter guidelines were fitted to contour-plot valleys showing how optimal parameters vary with K, combining analytic scaling estimates with empirical convergence behavior.Experiments used training-set sizes K ∈ {5, 10, 20}, 20 random ensembles per size, and 500 CDL iterations over parameter grids.
  • 2) Parameter Selection Guidelines:: The guidelines are reliable primarily for similarly pre-processed natural images and sparsity parameter λ = 0.1, although the derived scaling properties remain valid with different constants.FISTA is more sensitive to L than ADMM methods are to their penalty parameters.
  • VIII. CONCLUSIONS: FISTA provides the best serial dictionary update for masked and mask-free CDL, while consensus-based approaches provide the best parallel time performance in the respective settings.The mask-free parallel winner uses consensus with the alternative CDL structure, while masked CDL favors hybrid mask decoupling/consensus.
  • (Supplementary Material): Supplementary material documents the study context, grid-search surfaces, and analytic scaling derivations based on changing K by replicating identical data.The grid searches evaluate CDL functional values after fixed iterations across sparse-coding and dictionary-update parameters, while the analytic setup removes image-characteristic complexities.

A. ADMM Sparse Coding … D. FISTA Dictionary Update

The sections analyze how replicating training data affects augmented Lagrangians, gradients, and optimal algorithm parameters across ADMM and FISTA updates. The expected scaling differs by method: some parameters remain constant, while others scale linearly with the number of training images.

  • A. ADMM Sparse Coding: The ADMM sparse-coding formulation uses an augmented Lagrangian containing data fidelity, an ℓ1 penalty, and a quadratic constraint term.The displayed formulation includes 2 ∥Dx −s∥2 2, 2λ ∥y∥1, and 2ρ 2 ∥x −y + u∥2 2.
  • A. ADMM Sparse Coding: For ADMM sparse coding, replicating the training data doubles the augmented Lagrangian without changing the penalty parameter.Thus, the optimal penalty parameter ρ is expected to remain constant as K changes.
  • B. Equality Constrained ADMM Dictionary Update: The equality-constrained dictionary-update augmented Lagrangian combines data fidelity, the constraint indicator ιCPN(g), and a quadratic penalty involving d −g + h.This formulation is the basis for the stated penalty-parameter scaling under replicated training data.
  • B. Equality Constrained ADMM Dictionary Update: For equality-constrained ADMM dictionary updates, replicating the training data doubles the augmented Lagrangian when the penalty parameter is also doubled.The optimal penalty parameter is therefore expected to scale linearly with K.
  • C. Consensus ADMM Dictionary Update: The consensus ADMM dictionary-update formulation includes data fidelity, ιCPN(g), and a quadratic term involving d −Eg + h.The corresponding quadratic coefficient is shown as 2σ 2.
  • C. Consensus ADMM Dictionary Update: For consensus ADMM dictionary updates, replicating the training data doubles the augmented Lagrangian while leaving the penalty parameter σ unchanged.The optimal σ is therefore expected to remain constant as K changes.
  • D. FISTA Dictionary Update: In FISTA dictionary updates, replicating the training data doubles the gradient in the DFT domain.To preserve the same gradient step, the step parameter must be halved, so the inverse step-size parameter L is expected to scale linearly with K.

E. Mask Decoupling ADMM Sparse Coding · F. Mask Decoupling ADMM Dictionary Update · G. Hybrid Consensus Masked Dictionary Update

The three masked ADMM formulations analyze how replicating training data from K = 1 to K = 2 affects their augmented Lagrangians and optimal penalty parameters. Sparse coding and hybrid consensus preserve the expected penalty parameter, whereas the block-constraint dictionary update does not without reformulating the constraint.

  • E. Mask Decoupling ADMM Sparse Coding: The masked MMV CBPDN sparse-coding derivation uses an augmented Lagrangian and omits a final term that does not affect its minimizer.The K = 1 and K = 2 cases are related by replicating the training data.
  • E. Mask Decoupling ADMM Sparse Coding: For masked sparse coding, the K = 2 augmented Lagrangian is twice the K = 1 form with the same ρ, so the optimal penalty parameter is expected to remain constant.This expectation applies when changing the number of training images K.
  • F. Mask Decoupling ADMM Dictionary Update: The masked dictionary-update derivation uses a Block-Constraint ADMM augmented Lagrangian and omits a final term that does not affect its minimizer.The construction considers K = 1 and forms K = 2 by replicating the training data.
  • F. Mask Decoupling ADMM Dictionary Update: For the block-constraint dictionary update, K = 2 combines doubled K = 1 terms with another unchanged term, preventing a simple σ-scaling rule.Thus, the optimal penalty parameter σ has no simple scaling relationship with the number of training images K.
  • F. Mask Decoupling ADMM Dictionary Update: A scaling relationship for σ can be obtained by replacing g′ 0 = d′ with the equivalent constraint 2g0 = 2d, or more generally Kg0 = Kd.The scaled dual variable h0 must also be appropriately rescaled so the problematic term scales like the others.
  • G. Hybrid Consensus Masked Dictionary Update: The hybrid consensus masked dictionary-update derivation uses an ADMM consensus augmented Lagrangian, omits a final minimizer-irrelevant term, and constructs K = 2 by replicating training data.The K = 1 construction assumes E = I.
  • G. Hybrid Consensus Masked Dictionary Update: For hybrid consensus masked dictionary update, the K = 2 augmented Lagrangian is twice the K = 1 form with the same σ, so the optimal penalty parameter is expected to remain constant.This expectation concerns changing the number of training images K.

SIV. EXPERIMENTAL SENSITIVITY ANALYSIS · SV. LARGE TRAINING SET EXPERIMENTS · A. CDL without Spatial Mask

The experiments assess parameter sensitivity across training-set sizes and compare dictionary-learning methods on larger datasets. Cns-P generally provides the strongest convergence and testing performance, while FISTA is less stable and Papyan et al. is slow in runtime and weaker on testing.

  • SIV. EXPERIMENTAL SENSITIVITY ANALYSIS: 20 image subsets were evaluated at each training-set size K ∈ {5, 10, 20} using box plots of normalized functional values across parameter settings.The plots show medians, quartiles, and full variation for each parameter value.
  • SIV. EXPERIMENTAL SENSITIVITY ANALYSIS: FISTA has highly skewed sensitivity plots for L because convergence requires L to meet or exceed the gradient Lipschitz constant.The threshold indicating a behavioral change can be estimated in these experiments, although the constant is not always computable.
  • SV. LARGE TRAINING SET EXPERIMENTS: The large-set experiments used 25, 100, and 400 images at 1024 × 1024, 512 × 512, and 256 × 256 pixels, respectively.These combinations maintain a constant number of training-set pixels and use identically pre-processed MIRFLICKR-1M images.
  • SV. LARGE TRAINING SET EXPERIMENTS: Comparisons included the publicly available implementation of Papyan et al., whereas Šorel and Šroubek and Heide et al. were omitted because acceptable results could not be obtained.The omitted methods were very slow, with partial results after four days still noisy and far from convergence.
  • A. CDL without Spatial Mask: Cns-P consistently converged smoothly to the smallest or near-smallest training functional and exhibited the fastest convergence, except for the K = 25 case in Fig. S16.FISTA showed initial and final oscillations but reached similar final functional values, while Papyan et al. converged rapidly in iterations but was slowest in runtime.
  • A. CDL without Spatial Mask: Backtracking removes FISTA’s instability but tends to produce smoother convergence toward a larger functional value because it only increases L.For nonmonotone methods such as FISTA, the solution trajectory must therefore be considered when evaluating convergence.
  • A. CDL without Spatial Mask: Cns-P also achieved the best testing performance, followed by FISTA, while Papyan et al. was consistently worse than both methods.The testing plots used partial dictionaries from training and measured the CBPDN functional on the same additional 20-image test set.
  • A. CDL without Spatial Mask: Cns-P and FISTA time per iteration scale approximately linearly with the number of training pixels NK, with slight deviations attributed to FFT complexity of N log N.Because these algorithms also scale linearly with K, the results imply approximately linear scaling with image size N.

B. CDL with Spatial Mask … SVIII. MULTI-CHANNEL EXPERIMENTS

Across masked, scaling, comparative, and multi-channel experiments, the proposed methods generally perform competitively or better, while implementation and normalization issues affect some comparisons. Cns-P and FISTA also support multi-channel learning with moderate additional cost, with Cns-P slightly better on testing.

  • B. CDL with Spatial Mask: Masked experiments used common random masks with 25% zero entries across image sets of 1024 × 1024, 512 × 512, and 256 × 256 pixels.The corresponding results resembled those obtained for the unmasked variants.
  • B. CDL with Spatial Mask: Testing results for K = 400, 256 × 256 images were better for all methods, while masked Cns-P and M-FISTA substantially outperformed masked Papyan et al.Overfitting affected the proposed methods for K = 100 and K = 25, but less than in the unmasked cases.
  • B. CDL with Spatial Mask: Time per iteration for M-Cns-P and M-FISTA behaved similarly to unmasked variants when N × K remained unchanged.The masked–unmasked time difference was larger for M-FISTA than for M-Cns-P.
  • SVI. SCALING WITH DICTIONARY SIZE: All three methods exhibited linear scaling with the number of filters M in experiments using M ∈ {50, 100, 200, 500}.The comparison used 11 × 11 filters, K = 40 images, and 500 training iterations.
  • SVI. SCALING WITH DICTIONARY SIZE: DFT-domain methods were roughly independent of filter size and readily supported multi-scale dictionaries, whereas Papyan et al.’s spatial-domain method became more expensive and harder to extend.The experiments described here did not directly address filter-size scaling.
  • SVII. ADDITIONAL ALGORITHM COMPARISONS: Cns-P, FISTA, and Papyan et al. had comparable training performance, whereas Heide et al. converged slowly and Šorel–Šroubek’s apparently lower values were not comparable because filters were improperly normalized.FISTA initially exhibited oscillatory behavior, and Heide et al.’s code could not be run for a full 500 iterations.
  • SVII. ADDITIONAL ALGORITHM COMPARISONS: Cns-P and FISTA produced the smallest test-set CBPDN functional values, followed by Papyan et al., while Šorel–Šroubek and Heide et al. performed much worse.Heide et al.’s highly oscillatory evolution was plotted using the best value obtained up to each iteration.
  • SVIII. MULTI-CHANNEL EXPERIMENTS: For multi-channel learning, Cns-P required about 2/3 and FISTA about 3/4 of the corresponding greyscale computation time, despite using three times more training data.With M = 64, 8 × 8 filters, C = 3 channels, and K = 40 color images, Cns-P performed slightly better than FISTA on testing.
Loading 1709.02893v5…