{"id":"e3a223b7-200c-45ae-9a70-ddd1618b86f4","arxiv_id":"1909.00145","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A spatial-domain solver that randomly subsamples sparse-code coordinates each iteration reports 2x to 6x speedups over Fourier-domain convolutional sparse coding baselines with comparable quality, and scales to over-complete dictionary learning from thousands of images.","lead":"The paper shows that convolutional sparse coding, an image model built from small learned filters, can be trained much faster by randomly picking small pieces of the representation to update at each step. This speed-up allows over-complete dictionaries to be learned from thousands of images, improving reconstruction quality in tasks like image inpainting.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central speed/quality claim rests on an unproven and plausibly biased zero-imputation of unsampled code entries; no test establishes equal final quality at matched wall-clock time.","rationale":"I read the paper in good faith: the algorithm is clearly described, the spatial-domain motivation is legitimate, and the reported speedups are plausible if the subsampling heuristic works. The load-bearing weakness is not a logical contradiction but an unsupported empirical generalization: the sparse-support observation in Sec. 3.1 does not imply that uniformly sampling p% of code coordinates over iterations yields an unbiased or even convergent estimate of the original CSC solution. The zero-imputation in Eq. (4) makes this especially concerning, because unsampled active coordinates are actively erased before each dictionary update. The reader's weakest_assumption pointed at the same reliance on sparsity, so I partly agree; I sharpen it by identifying the specific zero-imputation bias and the per-iteration versus total-time gap. Since the paper is a short conference-style report with no code or supplement available, conditional acceptance with a request for these checks remains the appropriate verdict. I would not reject outright, because the experimental trend is consistent and the mechanism could be repaired by carrying over unsampled coordinates or by adding a proper convergence guarantee.","tokens_in":10836,"tokens_out":7547,"duration_ms":129879,"concrete_test":"Re-run the fruit/city batch experiments with SBCSC at p=0.1 and p=1 over at least 20 random seeds, using a matched stopping rule, and record the value of the original objective in Eq. (1) and held-out reconstruction PSNR. If the p=0.1 mean final objective is more than 1% worse than the p=1 value, or the held-out PSNR drops by more than 0.5 dB, the 'without losing quality' claim fails. As a mechanism check, also run a variant of Eq. (4) that keeps unsampled coordinates at their previous values; if that variant matches p=1 quality at lower cost, the zero-imputation bias is the culprit.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim requires that a random p-fraction of code coordinates can be used without losing learning quality. The paper's only support is the sparsity observation in Sec. 3.1 ('99.5% entries are not informative') plus the experiments in Sec. 4. That observation concerns the final solution's support, not the behavior of the subsampled iterates, so it does not by itself justify the sampler. More concretely, Eq. (3)-(4) set z_t = M_t^T \\tilde z_t, so every coordinate not drawn in iteration t is reset to zero before the dictionary update (5). This is not randomized coordinate descent with a valid stochastic-gradient estimator: a coordinate that was active in an earlier iteration is re-zeroed in roughly 1-p of all iterations, so the dictionary update is computed from systematically zero-imputed codes. No bound on the resulting bias is given; Sec. 3.1 only asserts that convergence 'will not be significantly affected' and defers to experiments. In addition, the runtime comparison in Sec. 4.2 is reported per iteration ('2x speedup over ... frequency-domain solver for one iteration'), while Fig. 1 shows that smaller p values reach a higher objective and converge more slowly per iteration. The total-time advantage at equal final quality is therefore not established by the reported numbers. Without error bars, seeds, code, or the referenced supplement, the equal-quality half of the claim is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11140,"tokens_out":2972,"duration_ms":53765,"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":[{"comment":"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.","section":"§3.1, Eqs. (3)–(4)"},{"comment":"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.","section":"§4.2, Fig. 1 and text"},{"comment":"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.","section":"§4.3, Fig. 4 and Fig. 3"},{"comment":"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.","section":"§4.1–§4.3"}],"minor_comments":[{"comment":"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).","section":"§2, Eq. (2)"},{"comment":"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 ...'.","section":"§3.2, Algorithm 1"},{"comment":"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.","section":"§4.2, Fig. 1"},{"comment":"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.","section":"§4.3, Fig. 5"},{"comment":"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.","section":"§4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a workshop-level contribution (VMV 2019) and the core idea is interesting, but the current evidence is not sufficient for a rigorous journal publication. The main issues—per-iteration runtime comparisons, lack of matched-quality timing, no error bars, and the unaddressed zero-imputation bias—are correctable within the manuscript's scope, so major revision is appropriate. I would also encourage the authors to release code and the supplement, as the manuscript currently makes reproducibility difficult."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look for anyone working on convolutional sparse coding or stochastic dictionary learning. The core idea is a randomized coordinate-subsampling strategy for the code subproblem, solved in the spatial domain, with batch and online variants. This combination is new; prior online CSC methods don't subsample code coordinates, and prior subsampling methods (e.g., Mensch et al.) target different problems. The complexity analysis is plausible, and the experiments show real speedups on fruit, city, and ImageNet patches, plus an interesting over-complete dictionary demonstration.\n\nThe main soft spot is the zero-imputation step in Eq. (4). Setting every unsampled code coordinate to zero before the dictionary update is not a standard stochastic-gradient estimator with a known bias. The paper's sparsity observation -- that 99.5% of final codes are non-informative -- concerns the converged solution, not the intermediate iterates, so it doesn't directly justify the sampler. No theorem quantifies how the subsampling rate p affects convergence or final quality. This is the load-bearing part of the headline claim, and it rests on experiments alone.\n\nThe experiments themselves could be stronger. They are single-run, with no error bars or seeds. No code or data are released, and the referenced supplement is missing. The runtime comparison in Sec. 4.2 is reported per iteration, while the convergence plots show that smaller p reaches a higher objective and converges more slowly. The total wall-clock time to reach a fixed objective is not carefully reported, so the 'without losing learning quality' half of the claim is not fully established. The recommended range p = 0.1-0.2 is selected from the same experiments used to demonstrate it.\n\nThese are not fatal objections. The algorithmic idea is clean, the writing is clear, and the experiments do support a more modest claim: with a carefully chosen sampling rate, the spatial-domain subsampling approach is competitive in total time with Fourier-domain solvers, with comparable (not identical) objectives. That is still a useful result.\n\nWho is this for? The CSC and sparse dictionary learning community, and anyone interested in stochastic subsampling tricks for large-scale optimization. I would send it to a serious referee rather than desk reject, but the referee should require code, error bars, and a total-time comparison at matched reconstruction quality. As is, I would treat the equal-quality speedup claim with caution.","headline":"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.","tokens_in":11660,"tokens_out":2675,"would_cite":false,"duration_ms":25385,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["convolutional sparse coding","stochastic optimization","random subsampling","spatial-domain solver","online dictionary learning","over-complete dictionary","image inpainting","LASSO"],"falsifier":"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.","tokens_in":10636,"feed_emoji":"⚡","tokens_out":7402,"duration_ms":61354,"temperature":0.7,"pith_summary":"This paper tries to establish that the spatial-domain solvers for Convolutional Sparse Coding, traditionally much slower than Fourier-domain solvers, can be made faster than those solvers by randomly subsampling the sparse codes at every iteration. The reason this works, the authors argue, is that CSC is over-parameterized and the codes are extremely sparse: for $K=100$ filters, 99.5% of code entries are non-informative, so a random $p$-fraction of coordinates suffices to represent the signal. A batch algorithm and an online algorithm built on this trick are reported to run faster than state-of-the-art frequency-domain baselines at comparable reconstruction quality, and the online variant scales to learning an over-complete 400-filter dictionary from a thousand images. If correct, this makes the spatial domain attractive again for unsupervised dictionary learning, sidestepping circular-boundary artifacts and exploiting the small support of filters.","feed_headline":"Random code sampling makes CSC solvers 2-6x faster","feed_subtitle":"Sampling 10% of sparse code entries per step beats Fourier-domain solvers in time, at matching quality.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduces the spatial-domain CSC formulation and the fruit and city datasets used in the experiments","marker":"[ZKTF10]"},{"why":"establishes the fast frequency-domain ADMM approach for CSC that the new solver is designed to beat","marker":"[BEL13]"},{"why":"provides the fast flexible frequency-domain solver used as the batch-mode state-of-the-art baseline","marker":"[HHW15]"},{"why":"represents the frequency-domain approach whose full-support dictionary update motivates the spatial-domain update on filter support","marker":"[Woh16]"},{"why":"supplies the online dictionary learning framework with surrogate statistics that the online extension adapts","marker":"[MBPS09]"},{"why":"develops the surrogate-matrix online learning theory for sparse coding that underpins the SOCSC dictionary update","marker":"[MBPS10]"},{"why":"is the online frequency-domain CSC method used as the baseline for the SOCSC runtime and quality comparison","marker":"[LGCWY18]"},{"why":"introduces the subsampling oracle for stochastic Frank-Wolfe that motivates updating only a random subset of variables each iteration","marker":"[RSPS16]"},{"why":"provides the large-scale image patches used to learn the over-complete dictionary","marker":"[DDS09]"}],"fun_headline_variants":["Random subsampling makes sparse coding 2-6x faster","Sampling 10% of code entries speeds up CSC 2-6x","Random code subsampling: CSC solvers 2-6x faster","CSC subsampling: 2-6x speedup with no quality loss","Stochastic CSC: random code sampling beats FFT solvers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random subsampling makes sparse coding 2-6x faster","Sampling 10% of code entries speeds up CSC 2-6x","Random code subsampling: CSC solvers 2-6x faster","CSC subsampling: 2-6x speedup with no quality loss","Stochastic CSC: random code sampling beats FFT solvers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001249,"raw_usage":{"total_tokens":5118,"prompt_tokens":940,"completion_tokens":4178,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":4082}},"tokens_in":556,"tokens_out":4178,"duration_ms":26757,"temperature":1.0,"reasoning_tokens":4082,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T06:00:43.007365+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}