{"id":"ee53282e-4b73-4cc2-b732-9be4600cbd75","arxiv_id":"2506.05617","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A local Fourier analysis algorithm computes the exact singular values of a periodic-boundary convolution in O(N) time, improving on the FFT-based O(N log N) approach.","lead":"This paper introduces a faster way to compute all singular values of a convolutional layer by analyzing it frequency-by-frequency, avoiding the FFT step of prior methods. For large images the new method cuts the asymptotic cost from O(N log N) to O(N), which matters for spectral regularization, robustness checks, and compression of neural networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"For zero-padded CNNs the method is an unquantified approximation: Section IV-A gives only sorted-spectrum plots and no error bound or singular-vector check, so the 'exact SVD of convolutional mappings' claim does not cover standard CNN layers.","rationale":"I read the central claim in good faith: under periodic boundary conditions, Algorithm 1 computes the exact singular values of the convolutional mapping by diagonalizing the operator into frequency blocks, and the O(nm c^3) complexity for the per-frequency SVDs is real. The weak point is not the algebra but the mapping from the theorem to the CNN setting. Real CNN layers pad with zeros, not periodically, and the paper's only support for the transfer is Figure 6, which plots sorted singular values for a few small input sizes and explicitly admits that boundary conditions 'clearly affect the approximation quality' for small n. Sorted spectra can hide large individual mismatches due to crossings, and no singular-vector comparison is made, even though the abstract promises singular vectors if needed. This makes the practical claim unsupported in exactly the regime where CNNs operate. I considered whether the 'complete SVD' wording overstates the method because materializing global singular vectors costs O(n^2 m^2 c^3), but the paper's own emphasis on computing singular values 'without forming the global singular vectors' suggests the intended complexity claim is about singular values, so I did not make that the primary objection. The reader's conditional verdict is appropriate; my concern is the same root assumption, so no verdict change is needed.","tokens_in":12255,"tokens_out":16272,"duration_ms":178182,"concrete_test":"Reproduce Section IV-A at n in {8,16,32,64,128,256}, c=16, with random Gaussian weights: compute sigma_LFA from Algorithm 1 (periodic) and sigma_Dir from the explicit sparse zero-padded matrix (scipy.sparse.linalg.svds for large n). Report max_i |sigma_LFA^(i)-sigma_Dir^(i)| / sigma_max(Dir), the 1-Wasserstein distance between the two ordered spectra, and the principal-angle subspace distance between the top-k (k in {5,50,500}) left and right singular subspaces. If for n>=64 all relative errors are below, say, 1% and subspace distances are small, the practical claim is supported; otherwise the paper must state that the method returns a periodic-boundary approximation with no vector-level guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The periodic-boundary theorem in Section III(c) is correct: for a circular convolution, Fourier modes are invariant subspaces, so per-frequency SVDs of the symbol A_k give the exact singular values. The load-bearing gap is the transfer to CNNs, which use zero padding (Dirichlet). Section III(e) acknowledges this, and Section IV-A is the only evidence; it plots sorted singular values for n in {4,8,32} and states that boundary conditions 'clearly affect the approximation quality' for small n. No quantitative error bound, no asymptotic rate, and no input-size threshold are given. Worse, the comparison is only between sorted spectra: for applications named in the paper (low-rank compression, pseudo-inverse), the actual singular vectors matter, and no experiment measures whether the periodic singular vectors approximate the Dirichlet ones. Since the abstract promises 'the entire set of singular values — along with the corresponding singular vectors if needed — for high-dimensional convolutional mappings,' the standard zero-padded CNN layer is exactly the case where the claim is not established. This does not invalidate the periodic-boundary result, but it means the headline contribution is a conditional approximation for real CNNs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a local Fourier analysis (LFA) based method for computing the singular value decomposition of convolutional mappings. Exploiting translation invariance, the method evaluates the symbol A_k = sum_y M_y exp(2π i <k,y>) for each frequency k and performs an SVD of each c_out × c_in block, yielding the complete SVD under periodic boundary conditions. The authors derive an O(N c^3) complexity for the singular value computation, improving on the FFT-based approach of Sedghi et al. by a logarithmic factor, and present runtime experiments on a CPU for input sizes up to n = 16,384. The paper also empirically compares singular value spectra under periodic and zero-padded (Dirichlet) boundary conditions, finding qualitative agreement for large input sizes.","tokens_in":12485,"tokens_out":5714,"duration_ms":63822,"significance":"If the claims are appropriately qualified, the periodic-boundary result is a clean and useful contribution: the per-frequency block-diagonalization of a convolutional operator is derived self-containedly, and the O(N) scaling (for fixed kernel and channel sizes) over the FFT baseline is theoretically and experimentally supported. The derivation is free of fitted parameters, and the runtime study covers a wide range of input sizes. The main caveat is that standard CNN convolutions use zero padding, not periodic boundary conditions, and the paper's evidence for transferring the exact periodic-boundary result to the zero-padded case is only qualitative. Since the named applications (low-rank compression, pseudo-inverses) require singular vectors, not just the sorted spectrum, this gap is load-bearing for the paper's headline claim about real CNNs.","major_comments":[{"comment":"The transfer from periodic to zero-padded (Dirichlet) boundary conditions is not quantitatively established. The paper only plots sorted singular value spectra for n = 4, 8, 32 and states that small inputs are 'clearly affected'; there is no error bound, no asymptotic rate, and no input-size threshold. Moreover, the comparison is only between sorted spectra, while the applications advertised in the introduction (low-rank compression, pseudo-inverse computation) require the actual singular vectors. The abstract and conclusion should either state clearly that the exact SVD claim holds only for periodic boundary conditions, or provide a quantitative analysis of the approximation error for zero-padded convolutions, including a check of the singular vectors.","section":"Section IV-A and Section III(e)"},{"comment":"The stated complexity for unequal channel dimensions is incorrect. For a cout × cin matrix, the SVD cost is O(cout^2 cin) when cin ≥ cout and O(cout cin^2) when cin ≤ cout (with the usual convention for rectangular SVD). The table gives O(nm cin^2 cout) for cin ≥ cout, which swaps the roles of cin and cout. This should be corrected to O(nm cout^2 cin).","section":"Table I, row 'cin ≥ cout'"},{"comment":"The claimed O(N) complexity omits the dependence on the kernel support size. Each symbol B_{i,j} is a sum over y ∈ N of the cout × cin matrices M_y times an exponential factor, so the per-frequency cost is O(|N| cin cout) before the SVD. The O(1) designation in line 4 is valid only when the kernel extent is treated as a fixed constant, as in typical small CNN kernels. This assumption should be stated explicitly in the complexity theorem and in the abstract, since without it the comparison to the FFT-based method is not complete.","section":"Section III(d), Algorithm 1, line 4"}],"minor_comments":[{"comment":"The sentence 'We verified that the time required to compute the SVD decreases as n increases' is contradicted by Table II, where total runtime increases monotonically with n (from 2.30 s at n=256 to 7521.93 s at n=16384). The authors likely mean that the runtime gap or the per-singular-value cost decreases; please rephrase.","section":"Section V, Conclusion"},{"comment":"There is a typographical artifact at the end of the sentence 'without forming the global singular vectors ˆUk and ˆVk,.'; the stray comma should be removed.","section":"Section III(c)"},{"comment":"The example 'the computation of the singular values of a 1,024 × 1,024 matrix takes 0.30 seconds' would be clearer if it explicitly says that this is the explicit unrolled matrix size, not the input feature-map size, since the latter is used elsewhere in the same paragraph.","section":"Section IV-b, paragraph 2"},{"comment":"The speed-up factor column would benefit from an explicit statement that sFFT and sLFA include the transformation step, to align with the text in Section IV-b that timing starts before the transformation.","section":"Section IV-b, Table II"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the periodic-boundary core is sound, but the boundary-condition gap and the incorrect rectangular-complexity formula need to be addressed before publication. I would not reject the manuscript: the central periodic-boundary derivation is correct and the efficiency claim is credible for the stated setting. The main risk is overclaiming applicability to standard zero-padded CNNs without quantitative support."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing to know: the algorithm is correct and the complexity drop from O(N log N) to O(N) is real, but the exactness claim holds for periodic boundary conditions. For the zero-padded convolutions used in practice, the paper offers only empirical evidence, and not a quantitative error bound.\n\nWhat is genuinely new: Sedghi et al. already established that Fourier modes block-diagonalize a convolution. The extension here is that you can form the per-frequency symbol A_k directly, avoiding the FFT, and the per-frequency SVDs then give the whole spectrum. That is a clean and legitimate simplification, and the complexity analysis in Table I is correct for fixed kernel size. The memory-layout discussion is a nice practical detail, and the experiments match the theory: the speedup over FFT grows slowly with n, from 1.09 at n=256 to 1.44 at n=16384, consistent with removing a log factor.\n\nThe soft spot is the boundary-condition gap. Section III(c) is a textbook derivation for circular convolution. Section III(e) correctly notes that LFA assumes periodic BCs while CNNs use zero padding (Dirichlet). Then Section IV-A compares sorted spectra for n=4,8,32. That is the only evidence. For small inputs the spectra clearly differ; the paper says the effect 'disappears' with growing n, but there is no error bound, no rate, and no threshold. More importantly, for the applications the paper itself lists — low-rank compression and pseudo-inverses — the singular vectors matter, and no experiment checks whether the periodic singular vectors approximate the Dirichlet ones. So the practical claim is softer than the abstract's promise of an exact SVD for convolutional mappings.\n\nNone of this sinks the core result. The periodic-boundary algorithm is exact and the complexity analysis is sound. The missing piece is a quantitative statement about the periodic-to-Dirichlet transfer. Also minor: the complexity table drops the kernel-size dependence, and the runtime experiments use only c=16, so the channel dependence is untested.\n\nWho is this for: anyone doing spectral analysis of convolutional layers under periodic padding, or who wants a simple baseline for approximating spectra of standard CNN layers. It deserves a serious referee; I'd recommend sending it out, with the referee asked to press on the boundary-condition error bound and on a vector-accuracy check.","headline":"Correct and useful O(N) algorithm for periodic boundary conditions; the zero-padding transfer is empirical only, so the 'exact SVD' claim overreaches.","tokens_in":51,"tokens_out":3567,"would_cite":true,"duration_ms":58919,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F15","65T50","68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"A CNN convolution's entire singular-value spectrum can be computed by SVD-ing one small channel block per Fourier frequency, skipping the FFT log factor.","keywords":["singular value decomposition","convolutional neural networks","local Fourier analysis","convolution theorem","spectral norm","Fourier symbol","boundary conditions","computational complexity"],"falsifier":"For a small periodic convolution, form the explicit doubly block-circulant matrix and compare its full singular-value list to Algorithm 1's output for many random kernels; any mismatch beyond numerical precision would disprove the exactness claim. Separately, for a zero-padded convolution at $n=8$ or $n=16$, compare the LFA spectrum to the explicit sparse-matrix SVD: if the maximum relative deviation does not shrink as $n$ grows, the practical approximation claim for Dirichlet boundary conditions fails.","tokens_in":12087,"feed_emoji":"⚡","tokens_out":6271,"duration_ms":62021,"temperature":0.7,"pith_summary":"The paper shows that the complete singular value decomposition of a convolutional layer can be obtained by evaluating the layer's Fourier symbol at every discrete frequency and taking the SVD of the resulting $c_{out} \\times c_{in}$ block. This reduces the cost from the FFT-based $O(n^2 c^2(c+\\log n))$ to $O(n^2 c^3)$ for square inputs, with no log factor, and the same idea extends to rectangular inputs and unequal channel counts. The authors argue that this makes full spectral information accessible for convolutional layers whose explicit matrix form is far too large to store. They support the claim with a runtime analysis and numerical experiments, while acknowledging that the exactness relies on periodic boundary conditions rather than the zero padding used in most CNNs.","feed_headline":"Full SVD of a convolution, without the FFT log factor","feed_subtitle":"A per-frequency block SVD gives the full spectrum in O(nmc^3), beating FFT methods by a log factor.","key_machinery":"The load-bearing object is the Fourier symbol $A_k=\\sum_{y\\in\\mathcal{N}} M_y e^{2\\pi i\\langle k,y\\rangle}$, a $c_{out}\\times c_{in}$ matrix built from the $c_{out}\\times c_{in}$ kernel weights $M_y$ and the frequency $k$. Because the spatial Fourier modes are orthogonal and are eigenvectors of any shift-invariant convolution, the full operator splits into one such block per frequency; the whole spectrum is the union of the per-block spectra, and the global singular vectors are the per-block singular vectors transformed by the Fourier basis. This block diagonalization is what carries the complexity reduction: each block SVD costs $O(c^3)$ and there are $nm$ blocks, independent of any FFT log factor.","core_discovery":"The central claim is that a convolutional mapping $A: \\mathbb{R}^{m\\times n\\times c_{in}}\\to\\mathbb{R}^{m\\times n\\times c_{out}}$ is diagonalized by the Fourier basis in the spatial dimensions, so its singular values are exactly the union of the singular values of the symbols $A_k=\\sum_{y\\in\\mathcal{N}} M_y e^{2\\pi i\\langle k,y\\rangle}$ taken over all frequencies $k$ on the dual torus. Each symbol is only $c_{out}\\times c_{in}$, and its left and right singular vectors lift back to global singular vectors through the Fourier basis matrices $F^{c_{out}}_k$ and $F^{c_{in}}_k$. Algorithm 1 performs one SVD per frequency without ever forming the global matrix, and the paper proves the per-frequency computations have cost $O(1)$ in the spatial size, giving $O(nmc^3)$ overall for equal channels. This removes the $\\log n$ factor that the FFT-based approach incurs.","pith_inferences":["The exactness claim is cleanest for circular convolutions; applying the algorithm to zero-padded CNN layers is an approximation whose error the paper only observes empirically. A natural next step is deriving a quantitative bound on the spectrum perturbation in terms of kernel support and input size.","The lattice and crystal formulation suggests the same symbol-based SVD works for non-rectangular sampling patterns, so the method could extend to spherical or octagonal convolutions with only a change of the frequency grid.","One testable extension is to use the per-frequency singular vectors to build exact low-rank approximations of convolutional layers in the Fourier domain, which may compress models more effectively than spatial low-rank factorizations.","If periodic padding were adopted in network architectures, the SVD would be exact and differentiable, enabling spectral losses computed from the full spectrum rather than estimates of the largest singular value."],"forward_implications":["For a fixed channel count, computing all singular values of a convolutional layer becomes linear in the number of pixels, so spectra of layers with very large inputs become tractable.","The full spectrum, not just the largest singular value, can be used for spectral regularization, robustness certification, low-rank compression, and exact pseudo-inverse layers.","The speed-up over the FFT-based method grows with input size; the paper reports a measured factor of 1.09 at $n=256$ and 1.44 at $n=16{,}384$.","Because each frequency's SVD is independent, the computation is embarrassingly parallel and can be distributed across cores or devices.","The method also produces a memory layout that makes the subsequent SVD routine faster, further widening the runtime gap."],"supporting_citations":[{"why":"Establishes the FFT-based SVD method for convolutional layers that this paper improves upon by removing the log factor.","marker":"[6]"},{"why":"Supplies the lattice and crystal formulation of local Fourier analysis and the convolution theorem that the algorithm is built on.","marker":"[17]"},{"why":"Provides the dense SVD complexity bound $O(c^3)$ used in the runtime analysis.","marker":"[28]"},{"why":"Supplies the dense SVD routine used as the numerical baseline in the runtime experiments.","marker":"[29]"}],"fun_headline_variants":["Full SVD for CNNs in linear time, no FFT","Convolution SVD without the FFT log factor","Per-frequency SVD gives CNN spectrum in O(N)","Linear-time full spectrum for convolutional layers","Local Fourier analysis: O(N) SVD for CNNs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that periodic boundary conditions give the same singular-value spectrum as the zero padding used in real CNN layers; the paper only demonstrates this agreement empirically and notes that boundary conditions clearly affect accuracy for small inputs.","fun_headline_variants_meta":{"raw":{"variants":["Full SVD for CNNs in linear time, no FFT","Convolution SVD without the FFT log factor","Per-frequency SVD gives CNN spectrum in O(N)","Linear-time full spectrum for convolutional layers","Local Fourier analysis: O(N) SVD for CNNs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1789,"prompt_tokens":1004,"completion_tokens":785,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":707}},"tokens_in":620,"tokens_out":785,"duration_ms":7837,"temperature":1.0,"reasoning_tokens":707,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:12:54.589177+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small periodic convolution, form the explicit doubly block-circulant matrix and compare its full singular-value list to Algorithm 1's output for many random kernels; any mismatch beyond numerical precision would disprove the exactness claim. Separately, for a zero-padded convolution at $n=8$ or $n=16$, compare the LFA spectrum to the explicit sparse-matrix SVD: if the maximum relative deviation does not shrink as $n$ grows, the practical approximation claim for Dirichlet boundary conditions fails.","supporting_citations":[{"cited_title":"The singular values o f convolu- tional layers,","cited_arxiv_id":null,"evidence_quote":"Establishes the FFT-based SVD method for convolutional layers that this paper improves upon by removing the log factor."},{"cited_title":"Automated local fourier anal ysis (aLFA),","cited_arxiv_id":null,"evidence_quote":"Supplies the lattice and crystal formulation of local Fourier analysis and the convolution theorem that the algorithm is built on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the dense SVD complexity bound $O(c^3)$ used in the runtime analysis."},{"cited_title":"Array programming with NumPy,","cited_arxiv_id":null,"evidence_quote":"Supplies the dense SVD routine used as the numerical baseline in the runtime experiments."}],"review_version":1}