REVIEW 4 major objections 5 minor 32 references
Stochastic Convolutional Sparse Coding
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper claims that randomly subsampling sparse code coordinates each iteration lets a spatial-domain solver beat frequency-domain CSC solvers in runtime at equal quality, in both batch and online settings.
desk verdict A clean stochastic subsampling idea for spatial-domain CSC with plausible speedups, but the equal-quality claim rests on zero-imputed iterates and timing comparisons that need more support. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the random subsampling matrix $M_t$, a $pDK \times DK$ binary matrix with one 1 per row, regenerated at each iteration to select which code coordinates are updated. It does the work by shrinking the sparse-coding subproblem from $DK$ variables to $pDK$, making spatial-domain convolution competitive with Fourier-domain multiplication, and by letting the dictionary subproblem stay on the $M$-dimensional filter support instead of the full $D$-dimensional signal support. The online extension is carried by two surrogate matrices $C$ and $B$, updated as running averages of $(Z_t)^T Z_t$ and $(Z_t)^T x_t$, which replace storage of all past images in the dictionary update.
What would settle it
Run the stochastic solver at $p=0.1$ on data whose optimal codes are not highly sparse, for example with a very small sparsity penalty $\lambda$, and compare the training objective and reconstruction PSNR against the $p=1$ run; if the subsampled run falls well short while a frequency-domain baseline reaches the $p=1$ value, the sparsity premise fails. A more direct test is to compare the support of the full sparse-code solution with the positions randomly sampled by $M_t$: if informative coordinates are systematically missed for some images, the claimed quality preservation will not hold.
Extended reading notes
Core claim
The central claim is that random subsampling of code coordinates, encoded by a binary matrix $M_t$ that projects the current codes $z_t$ onto a randomly selected subspace, preserves the learning quality of CSC because the model is over-parameterized and the vast majority of code entries carry no information. With a subsampling rate between $p=0.1$ and $p=0.2$, the code-update LASSO is solved on only $pDK$ variables in the spatial domain, and the dictionary update works directly on the small filter support; the reported consequence is that the batch method runs about 2x faster per iteration than the frequency-domain baseline and about 6x faster than the non-subsampled spatial solver, while the online method runs about 6x faster than the online frequency-domain baseline at comparable objective and PSNR. The paper further claims that the online model, using surrogate matrices to accumulate statistics, learns a 400-filter over-complete dictionary from 1000 images, which yields sparser representations of natural images and better inpainting from 50% observed pixels.
Load-bearing premise
The load-bearing premise is that because the CSC model is over-parameterized and the codes are extremely sparse, a random $p$-fraction of code coordinates still represents the signal well at every iteration; the paper supports this only with empirical observations, and no theorem quantifies how $p$ affects convergence or final quality.
Editorial extensions
If this is right
- A subsampling rate between $p=0.1$ and $p=0.2$ gives an empirically good trade-off: around 3x or more speedup while still converging in roughly 10-12 iterations like frequency-domain solvers.
- The online stochastic algorithm, optionally with mini-batches of size $\eta=20$, gives about an order-of-magnitude speedup over $\eta=1$ and scales to thousands of training images where batch CSC is memory-limited.
- Over-complete dictionaries with 400 filters learned at this scale reduce the number of non-zero coefficients by 8-10% and raise reconstruction PSNR by about 1 dB over under-complete dictionaries, and they improve image inpainting quality.
- Because the whole pipeline stays in the spatial domain, it does not rely on circular boundary conditions and can directly benefit from sparse-LASSO accelerations such as safe screening and skip-update coordinate descent, which are unavailable to Fourier-domain formulations.
- The batch and online code updates both reduce to solving a highly sparse LASSO, so any improvement in sparse LASSO solvers immediately transfers to the proposed CSC methods.
Reading between the lines
- The same subsampling rationale should extend to audio, video, or volumetric signals, since the only property it depends on is the high sparsity fraction of the codes rather than image-specific statistics.
- A formal analysis linking the subsampling rate $p$ to convergence and final quality would be needed to guarantee the empirical trade-off; the paper deliberately leaves this as an experimental observation.
- The Bernoulli sampling could be replaced by importance sampling weighted by the magnitude of previously learned codes, potentially preserving quality at even smaller $p$.
- The reported 99.5% non-informative entry fraction suggests a two-phase strategy: identify the support of active codes once, then sample only among uncertain coordinates; this would turn the constant-factor speedup into an even larger one.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes stochastic spatial-domain solvers for Convolutional Sparse Coding (CSC) that randomly subsample a fraction p of the sparse code coordinates at each iteration, then update the dictionary from the zero-imputed codes. Two variants are presented: a batch method (SBCSC) and an online method (SOCSC) with surrogate matrices for streaming data. The central claim is that, with a suitable subsampling rate (p between 0.1 and 0.2), the spatial-domain solver is faster than state-of-the-art frequency-domain solvers while preserving learning quality. The authors report experiments on fruit/city datasets (10 images) and 1000 ImageNet patches, including convergence plots, runtime comparisons, and an over-complete dictionary (K=400) demonstration with an image inpainting application.
Significance. If the central claim holds, the paper offers a genuinely useful alternative to Fourier-domain CSC: it avoids circular boundary conditions, exploits the extreme sparsity of CSC codes, and scales online learning to large datasets. The randomized-subsampling idea is simple and the algorithm is clearly specified, with a plausible complexity analysis. The comparison against external baselines (Heide et al. for batch, Liu et al. for online) is appropriate, and the over-complete dictionary experiment is a nice illustration. However, the evidence for the speed/quality claim is currently incomplete: runtime comparisons are per-iteration rather than at matched final quality, there are no error bars or multiple seeds, the supplement containing solver details is not available, and the zero-imputation step in Eqs. (3)–(4) has no theoretical justification. These gaps must be addressed before the central claim can be accepted.
major comments (4)
- [§3.1, Eqs. (3)–(4)] The central speed/quality claim rests on the subsampling step, but the manuscript provides no theoretical or rigorous empirical justification that zero-imputing the unsampled code coordinates does not bias the dictionary update. In Eq. (4), every coordinate not drawn in iteration t is reset to zero for the subsequent dictionary update (5). This is not a standard unbiased stochastic-gradient estimator: a coordinate that was active in an earlier iteration is zeroed in roughly 1−p of all iterations, so the update is computed from systematically censored codes. Section 3.1 only asserts that convergence 'will not be significantly affected' based on the empirical observation that 99.5% of final code entries are non-informative; that observation concerns the final solution's support, not the behavior of the subsampled iterates. Please either provide a convergence/bias analysis (e.g., bounding the error introduced by zero-imputation as a function of p) or present experiments on multiple datasets with error bars that directly compare the proposed method against baselines at matched final objective/PSNR.
- [§4.2, Fig. 1 and text] The runtime comparison does not establish the claimed '2x speedup without losing learning quality' because it is reported per iteration, not as time-to-reach-the-same-final-quality. The text gives total times (170s vs 350s for 14 iterations), but Fig. 1 shows that smaller p values converge to a higher objective and converge slower per iteration. Thus the time needed to reach the same objective value or reconstruction quality may be larger than the per-iteration speedup suggests. Please report wall-clock time to reach a fixed objective value or a fixed PSNR, with multiple runs (different seeds) and standard deviations, for both the proposed and baseline methods.
- [§4.3, Fig. 4 and Fig. 3] The over-complete dictionary experiment compares the proposed K=400 dictionary against the baseline's K=100 dictionary, which is not a controlled comparison. The improved sparsity and PSNR shown in Fig. 3 could be due to the larger dictionary size rather than to the proposed subsampling method. To support the claim that SOCSC learns better dictionaries, please include a comparison with the same over-complete size (K=400) for the baseline online CSC method, or at least a K=100 comparison of SOCSC versus Liu et al. with identical dictionary size and training data.
- [§4.1–§4.3] The experimental validation is very limited and does not support the general claim of 'outperforming state-of-the-art frequency-domain solvers.' The batch and online comparisons use only the fruit dataset for runtime and objective plots, and the online large-scale experiment uses 1000 ImageNet patches. No error bars, no seeds, no code, and no supplement are provided, despite the text referring to 'supplementary materials' for solver details and robustness tests. Please provide the supplement or incorporate the missing details, and add experiments on additional standard datasets (e.g., city, or larger natural-image benchmarks) with multiple trials to quantify variance.
minor comments (5)
- [§2, Eq. (2)] There is a typo in the dimension of M_t: 'RpDk×DK' should likely be 'R^{pDK×DK}' (the subscript k is undefined and the notation is inconsistent with the surrounding text).
- [§3.2, Algorithm 1] The set notation 'p ={1,0.5,0.2,0.1,0.05}' is non-standard; use 'p ∈ {1, 0.5, 0.2, 0.1, 0.05}' or 'p is chosen from ...'.
- [§4.2, Fig. 1] The axis labels in Fig. 1 are unclear; the top-left plot appears to lack a y-axis label, and the top-right time axis is given in logarithmic scale but the units are not fully specified. Please clarify the figures and ensure all panels are legible.
- [§4.3, Fig. 5] The bottom panel of Fig. 5 appears to show '2 = 1 2 = 5 2 = 20' which is a rendering artifact of 'η = 1', 'η = 5', 'η = 20'. Please fix the LaTeX/math rendering.
- [§4.2] The phrase 'the comparison method uses a similar number of iterations as ours to reach convergence' is vague; please state explicitly how the stopping criterion was set for each method.
Circularity Check
No significant circularity: the central speed/quality claim is empirical and tested against external baselines, not defined in terms of the method's own output.
full rationale
No circular step is present. The paper's central claim, that a stochastic spatial-domain solver with a reasonable subsampling rate outperforms frequency-domain solvers in runtime without losing learning quality, is supported by experiments against external baselines: Heide et al. [HHW15] for batch mode and Liu et al. [LGCWY18] for online mode. The subsampling rate p is explicitly treated as a chosen hyperparameter tested over a grid (p = {1, 0.5, 0.2, 0.1, 0.05}); recommending p = 0.1-0.2 from the same experiments is ordinary hyperparameter selection, not a fitted input renamed as a prediction, and the paper's claim is explicitly conditional on a 'reasonable selection' of the rate. The sparsity observation in Section 2 (99.5% non-informative code entries) is an empirical motivation for the subsampling idea, not an assumption whose restatement is presented as a derived result. The zero-imputation update in Eq. (4) is a modeling choice without a formal convergence guarantee, but that is a correctness or robustness concern, not circularity. Citations to works with overlapping authorship, such as [HHW15] and [CSH17], are used as comparison baselines or application references; none of the load-bearing claims reduces to a self-citation. The runtime advantage is partly built into the algorithmic complexity, but the 'without losing learning quality' half is an external experimental comparison and is not forced by construction. Therefore the paper exhibits no significant circularity.
Assumptions & free parameters
free parameters (6)
- Subsampling rate p =
0.1 or 0.2 (recommended); tested {1, 0.5, 0.2, 0.1, 0.05}
- Sparsity penalty lambda =
1
- ADMM inner iterations =
10
- Augmented Lagrangian penalty rho =
10 (10*lambda)
- Over-relaxation parameter alpha =
1.8
- Mini-batch size eta =
Tested {1, 5, 20}
assumptions (4)
- domain assumption The sparse codes in CSC are highly sparse (about 99.5% of entries are non-informative for K=100), so a random p-fraction of code coordinates is sufficient to represent the signal at each iteration.
- domain assumption The CSC objective is approximately bi-convex and coordinate descent on alternating z and d subproblems converges to a good solution; the stochastic variant also converges.
- domain assumption Filter size M and number of filters K are small relative to signal dimension D (K approximately M, M much less than D), which justifies the complexity savings of spatial-domain processing.
- domain assumption The reported runtime comparisons against Heide et al. and Liu et al. are fair, meaning both methods are optimized to similar levels and run on the same hardware and software.
Cite this review
Pith. "Pith review of Stochastic Convolutional Sparse Coding." pith.science (2026). https://pith.science/paper/44NJ7MAX
@misc{pith2026190900145,
author = {Pith},
title = {Pith review of: Stochastic Convolutional Sparse Coding},
year = {2026},
howpublished = {\url{https://pith.science/paper/44NJ7MAX}},
note = {Machine review of arXiv:1909.00145}
}
read the original abstract
State-of-the-art methods for Convolutional Sparse Coding usually employ Fourier-domain solvers in order to speed up the convolution operators. However, this approach is not without shortcomings. For example, Fourier-domain representations implicitly assume circular boundary conditions and make it hard to fully exploit the sparsity of the problem as well as the small spatial support of the filters. In this work, we propose a novel stochastic spatial-domain solver, in which a randomized subsampling strategy is introduced during the learning sparse codes. Afterwards, we extend the proposed strategy in conjunction with online learning, scaling the CSC model up to very large sample sizes. In both cases, we show experimentally that the proposed subsampling strategy, with a reasonable selection of the subsampling rate, outperforms the state-of-the-art frequency-domain solvers in terms of execution time without losing the learning quality. Finally, we evaluate the effectiveness of the over-complete dictionary learned from large-scale datasets, which demonstrates an improved sparse representation of the natural images on account of more abundant learned image features.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION fin.entry.original add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 i...
-
[3]
: The tradeoffs of large scale learning
Bousquet O., Bottou L. : The tradeoffs of large scale learning. In Advances in neural information processing systems (2008), pp. 161--168
work page 2008
-
[4]
: Fast convolutional sparse coding
Bristow H., Eriksson A., Lucey S. : Fast convolutional sparse coding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2013), pp. 391--398
work page 2013
-
[5]
: High order tensor formulation for convolutional sparse coding
Bibi A., Ghanem B. : High order tensor formulation for convolutional sparse coding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2017), pp. 1772--1780
work page 2017
-
[6]
: Online learning and stochastic approximations
Bottou L. : Online learning and stochastic approximations. On-line learning in neural networks 17, 9 (1998), 142
work page 1998
-
[7]
Boyd S., Parikh N., Chu E., Peleato B., Eckstein J., et al. : Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning 3 , 1 (2011), 1--122
work page 2011
-
[8]
: Consensus convolutional sparse coding
Choudhury B., Swanson R., Heide F., Wetzstein G., Heidrich W. : Consensus convolutional sparse coding. In Proceedings of the IEEE International Conference on Computer Vision (2017), pp. 4290--4298
work page 2017
Show all 32 references
-
[9]
: Imagenet: A large-scale hierarchical image database
Deng J., Dong W., Socher R., Li L.-J., Li K., Fei-Fei L. : Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2009), pp. 248--255
2009
-
[10]
E., Viallon V., Rabbani T
Ghaoui L. E., Viallon V., Rabbani T. : Safe feature elimination for the lasso and sparse supervised learning problems. In Pacific Journal of Optimization (2012), pp. 667--698
2012
-
[11]
: Convolutional sparse coding for image super-resolution
Gu S., Zuo W., Xie Q., Meng D., Feng X., Zhang L. : Convolutional sparse coding for image super-resolution. In Proceedings of the IEEE International Conference on Computer Vision (2015), pp. 1823--1831
2015
-
[12]
: Fast and flexible convolutional sparse coding
Heide F., Heidrich W., Wetzstein G. : Fast and flexible convolutional sparse coding. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2015), pp. 5135--5143
2015
-
[13]
B., Guestrin C
Johnson T. B., Guestrin C. : Stingycd: Safely avoiding wasteful updates in coordinate descent. In International Conference on Machine Learning (2017), pp. 1752--1760
2017
-
[14]
D., Simsekli U., Gramfort A
Jas M., La Tour T. D., Simsekli U., Gramfort A. : Learning the morphology of brain signals using alpha-stable convolutional sparse coding. In Advances in Neural Information Processing Systems (2017), pp. 1099--1108
2017
-
[15]
: Frank- W olfe with subsampling oracle
Kerdreux T., Pedregosa F., d'Aspremont A. : Frank- W olfe with subsampling oracle. In International Conference on Machine Learning (2018), pp. 2591--2600
2018
-
[16]
Kavukcuoglu K., Sermanet P., Boureau Y.-L., Gregor K., Mathieu M., Cun Y. L. : Learning convolutional feature hierarchies for visual recognition. In Advances in neural information processing systems (2010), pp. 1090--1098
2010
-
[17]
Krizhevsky A., Sutskever I., Hinton G. E. : Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems (2012), pp. 1097--1105
2012
-
[18]
: Gradient-based learning applied to document recognition
LeCun Y., Bottou L., Bengio Y., Haffner P. : Gradient-based learning applied to document recognition. Proceedings of the IEEE 86, 11 (1998), 2278--2324
1998
-
[19]
: First-and second-order methods for online convolutional dictionary learning
Liu J., Garcia-Cardona C., Wohlberg B., Yin W. : First-and second-order methods for online convolutional dictionary learning. SIAM Journal on Imaging Sciences 11, 2 (2018), 1589--1628
2018
-
[20]
Lei L., Jordan M. I. : Less than a single pass: Stochastically controlled stochastic gradient. In Proceedings of Machine Learning Research (AISTATS) (2017)
2017
-
[21]
: Online dictionary learning for sparse coding
Mairal J., Bach F., Ponce J., Sapiro G. : Online dictionary learning for sparse coding. In International Conference on Machine Learning (2009), pp. 689--696
2009
-
[22]
: Online learning for matrix factorization and sparse coding
Mairal J., Bach F., Ponce J., Sapiro G. : Online learning for matrix factorization and sparse coding. Journal of Machine Learning Research (2010), 19--60
2010
-
[23]
: Dictionary learning for massive matrix factorization
Mensch A., Mairal J., Thirion B., Varoquaux G. : Dictionary learning for massive matrix factorization. In International Conference on Machine Learning (2016), pp. 1737--1746
2016
-
[24]
Peter S., Kirschbaum E., Both M., Campbell L., Harvey B., Heins C., Durstewitz D., Diego F., Hamprecht F. A. : Sparse convolutional coding for neuronal assembly detection. In Advances in Neural Information Processing Systems (2017), pp. 3678--3688
2017
-
[25]
J., Sra S., P \'o czos B., Smola A
Reddi S. J., Sra S., P \'o czos B., Smola A. : Stochastic frank-wolfe methods for nonconvex optimization. In 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (2016), pp. 1244--1251
2016
-
[26]
: Parallel coordinate descent methods for big data optimization
Richt\' a rik P., Tak\' a c M. : Parallel coordinate descent methods for big data optimization. Mathematical Programming 156, 1-2 (2016), 433--484
2016
-
[27]
: Convolutional sparse coding for high dynamic range imaging
Serrano A., Heide F., Gutierrez D., Wetzstein G., Masia B. : Convolutional sparse coding for high dynamic range imaging. In Computer Graphics Forum (2016), vol. 35, Wiley Online Library, pp. 153--163
2016
-
[28]
: Online learning and online convex optimization
Shalev-Shwartz S., et al. : Online learning and online convex optimization. Foundations and Trends in Machine Learning 4 , 2 (2012), 107--194
2012
-
[29]
: Mini-batch primal and dual methods for svms
Tak\' a c M., Bijral A., Richt\' a rik P., Srebro N. : Mini-batch primal and dual methods for svms. In International Conference on Machine Learning 28 (2013), 537--552
2013
-
[30]
: Efficient algorithms for convolutional sparse representations
Wohlberg B. : Efficient algorithms for convolutional sparse representations. IEEE Transactions on Image Processing 25, 1 (2016), 301--315
2016
-
[31]
T., Ni L
Wang Y., Yao Q., Kwok J. T., Ni L. M. : Scalable online convolutional sparse coding. IEEE Transactions on Image Processing 27, 10 (2018), 4850--4859
2018
-
[32]
D., Krishnan D., Taylor G
Zeiler M. D., Krishnan D., Taylor G. W., Fergus R. : Deconvolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2010), pp. 2528--2535
2010
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.