{"id":"c03755f8-b176-47ae-ae32-7305cded9f56","arxiv_id":"1908.02461","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"The paper adds an adaptive tuning loop to sparse fast Fourier transform that estimates sparsity by counting local maxima in a subsampled hashed grid.","lead":"ATSFFT is a new sparse fast Fourier transform that automatically figures out how many important frequencies a signal has, removing a key user input. The paper reports speedups of about ten times over the FFTW library on sparse image-like signals, but the core idea was published in the authors' own earlier conference work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The adaptive sparsity probe equates local-max count with sparsity k on the strength of one example and a hash function that does not map to 2D bins; this unproven link is the load-bearing step.","rationale":"The reader's REJECT verdict is justified. My stress-test pass found the same load-bearing weakness: the assertion that local-maximum count equals k is unsupported, and it is the hinge of the paper's claimed novelty. I add two concrete technical observations. First, the hash function of Eq. 8 maps to one integer coordinate rather than to a pair of bin indices, so it is not clear that the \"B×B matrix of local maxima\" is well defined from that hash; this compounds the unproven local-max identity. Second, the adaptive update rule is internally inconsistent: the prose and Eq. 12 say decrease B when r_i is small, but Algorithm 2 lines 8-16 decrease B when ratio is between delta1 and delta2 and increase it when ratio is outside, which is the reverse tendency for the small-ratio regime. Thus the central adaptive tuning procedure is not uniquely specified. The experimental section also compares against SFFT with implied correct k, so the claimed improvement could simply reflect SFFT being given an unfavorable setup; however, the decisive issue is the unsupported sparsity-detection mechanism itself. No code is provided and no formal verification exists. These issues jointly break the central claim as stated, so REJECT remains the appropriate verdict.","tokens_in":11535,"tokens_out":1754,"duration_ms":15890,"concrete_test":"Run a controlled simulation on synthetic N×N signals with known sparsity k (e.g., k=1, 2, 5, 10, 50, 100) and randomly placed non-zero coefficients with several hash/bin sizes B. Count local maxima in the hashed B×B matrix under the authors' pipeline (permute, flat-window filter, subsample, then count local maxima), and record the distribution of counts across random trials. If the count deviates from k by more than a small fraction, or if the count is not monotone in k, then the sparsity-probing mechanism in Section III.A fails. Also re-derive the update: check whether Algorithm 2 lines 8-16 and Eq. 12 give the same B sequence; they appear to be opposite conditions.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim is that ATSFFT detects the unknown sparsity k by counting local maxima of the hashed B×B spectrum. Section III.A asserts that \"after the execution of the hash function, the number of local maximum points is the same with the number of original image's non-zero coefficients in frequency domain\" and supports this only with a k=2 example. This identity is not a theorem and is not justified by the preceding lemmas. Moreover, the hash function given in Eq. 8, h(i,j)=round(sigma1*sigma2*i*j*B^2/N^2), maps every coordinate to a single integer in [N^2], not to a pair of indices in [B]×[B]. Its image is not naturally a B×B matrix, and it is not the standard two-dimensional binning that the seek-location stage needs for reversing the hash or for counting spatial local maxima. If the local-max count systematically departs from k, then the update rules in Eq. 12 (halve, keep, or double B depending on r_i) drive B to the wrong value, and the estimated sparsity and candidate locations are wrong. The Algorithm 2 description is also inconsistent with Eq. 12: lines 8-16 reverse the conditions by doubling B when the ratio changes a lot but halving it when the ratio is small, whereas Eq. 12 halves B for small r_i and doubles for large r_i; this contradiction means the proposed tuning mechanism is not even uniquely specified. Because no proof or controlled test of the local-max-to-k identity is provided, the adaptive sparsity detection upon which the whole contribution rests is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ATSFFT, an adaptive two-dimensional sparse fast Fourier transform whose main novelty is automatic detection of the unknown sparsity k. The algorithm is built on a hash-based binning procedure followed by adaptive tuning of the bin size B; the number of local maxima in the hashed B×B matrix is claimed to equal k. The paper reports experiments on synthetic k-sparse images comparing runtime, speedup, and error against SFFT and FFTW, claiming that ATSFFT controls error better than SFFT and achieves an order-of-magnitude speedup over FFTW. The central mechanism, the sparsity probe, is asserted rather than proved, and several technical details of the hash and tuning loop are not adequately specified.","tokens_in":11899,"tokens_out":9124,"duration_ms":90372,"significance":"If the sparsity-detection identity were proven and the algorithm fully specified, an adaptive sparse FFT for the unknown-sparsity setting would be a useful practical contribution. The paper does not, however, deliver such a proof or specification. The main claim rests on a single k=2 example, the hash function as written does not map to a two-dimensional bin grid, the tuning thresholds are ad hoc, and the paper's own error tables contradict the claimed error-control advantage. The manuscript's positive aspects are the clear identification of a real limitation in SFFT (the need to know k in advance) and a substantial set of runtime comparisons; however, without a valid sparsity-detection mechanism the central contribution is not established.","major_comments":[{"comment":"The central sparsity-detection claim—that after hashing, the number of local maxima in the B×B matrix equals the number of non-zero Fourier coefficients—is asserted with a single k=2 example and no proof. This identity is the load-bearing step of the adaptive tuning loop, and it cannot be taken as self-evident: collisions, filter leakage, and the choice of B can change the local-maximum count. Furthermore, h(i,j)=round(σ1σ2ijB^2/N^2) maps a coordinate (i,j) to a single integer in [B^2], not to a pair of bin indices in [B]×[B]; the paper does not state how this integer is converted to a 2D bin, nor does it define the reverse hash function needed to map candidate bins back to frequency coordinates. The algorithm is therefore not fully specified at its core.","section":"Section III.A, Eq. (8)"},{"comment":"The update rules for B and the thresholds δ1=2%, δ2=5%, ε1=1/2, ε2=1 are introduced without derivation, convergence analysis, or sensitivity study. The textual rationale (e.g., that a small value of r_i means B is 'adapted to the full scatter point set') is not connected to a formal model of how the local-maximum count depends on B, and no experiment isolates the tuning loop's behavior. I note that I do not find a contradiction between Algorithm 2 and Eq. (12); in terms of r_i, small r_i triggers B/2 and large r_i triggers 2B in both places. The problem is that neither the definition of r_i nor the threshold choices is justified, which is a major gap for an algorithm whose entire contribution is automatic sparsity detection.","section":"Section III.A, Eqs. (10)-(12)"},{"comment":"The conclusion that 'ATSFFT can control the error better than SFFT' is contradicted by the reported data. For N=2^12 with k=100, ATSFFT has error 3.69×10^-10 versus 2.38×10^-10 for SFFT; for k=400, 2.54×10^-5 versus 2.64×10^-6; for k=600, 4.73×10^-5 versus 1.27×10^-5. These entries show SFFT with strictly lower error, so the abstract and Section IV-C overstate the error-control advantage.","section":"Section IV, Table IV"},{"comment":"The claimed order-of-magnitude speedup over FFTW is not uniform. At N=2^8, SFFT/FFTW is 0.2 and ATSFFT/SFFT is 10.9, giving ATSFFT only about 2.2× over FFTW. The paper provides no error bars, no statistical significance tests, and no complexity bound for the adaptive loop, so the performance claims are not established across the reported parameter range.","section":"Section IV-B, Table I"},{"comment":"All experiments use exactly k-sparse synthetic images with random support and unit magnitudes. This is the most favorable regime for the unproven local-maximum-count identity, and it does not test the method's stated motivation of handling real images with approximate frequency sparsity. No experiment reports the accuracy of the sparsity estimate k_i itself, so there is no direct evidence that the adaptive probe detects k correctly.","section":"Section IV"}],"minor_comments":[{"comment":"The conclusion refers to 'the paper in Section II-B', which is incorrect; it should refer to the conclusion section.","section":"Section V"},{"comment":"There are numerous typographical errors ('tow-dimensional', 'practival', 'equiped', 'sigmal', 'sparisty', 'Morever') and inconsistent notation ('A TSFFT' vs 'ATSFFT') that should be corrected.","section":"Throughout"},{"comment":"The text says 'By applying convolution of (8) and (9)', but the filter and window are defined in Eqs. (6) and (7); Eq. (8) is the hash function introduced later.","section":"Section II.A"},{"comment":"The caption and text disagree about the figure number, the caption says '2D-SFT' instead of '2D-SFFT', and Figure 5's caption appears without the corresponding plot in the text.","section":"Figures 4 and 5"},{"comment":"The citation placeholder 'radio astronomy[reference]' should be completed.","section":"Introduction"},{"comment":"The variable names (sigmal, x samp, ratio) are undefined or inconsistent with Section III.A's r_i, and the role of initial k0 in the first iteration is not explained.","section":"Algorithm 2"}],"recommendation":"reject","confidential_remarks":"This manuscript is a lightly revised conference-style paper whose central novelty is an unproven heuristic: the number of local maxima in a hashed B×B spectrum equals the unknown sparsity k. The hash function as written is mathematically incomplete, the adaptive tuning rules are ad hoc, and the paper's own error tables contradict the main error-control claim. These are load-bearing issues that cannot be fixed by local edits within the current manuscript's scope. I recommend rejection, though a substantially revised version with a correct hash, a proof or rigorous numerical validation of the sparsity-detection identity, and a broader experimental evaluation could be worth reviewing."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the central new mechanism — estimating unknown sparsity k by counting local maxima of the hashed spectrum — rests on an assertion with a single k=2 example as support, and the hash function in Eq. 8 does not, as written, map coordinates to a B×B grid. The adaptive-tuning idea also already appeared in the authors' own PCM 2017 paper, so this arXiv submission is mostly an extended experimental write-up.\n\nWhat the paper does well. The 2D SFFT pipeline — random permutation, flat Gaussian window, subsampling, and the seek-location/estimate-coefficient loops — is presented clearly, and Lemma 1 is standard. The experimental sweep is genuinely broad: image sizes from 2^8 to 2^13, k from 50 to 1000, runtime, speedup, and error tables. For someone implementing or benchmarking sparse 2D FFT, that data has real value, and the motivating problem — SFFT normally needs k in advance — is important.\n\nThe soft spots, in proportion. First and most serious, Section III.A asserts that after hashing, the number of local maximum points equals the number of non-zero coefficients. This is the load-bearing step for the whole adaptive scheme, and it is supported only by a k=2 example. No proof, no probabilistic argument, no discussion of what happens when two coefficients collide or a blob splits. Second, Eq. 8's hash function returns a single integer, not a pair of bin indices in [B]×[B]; you need an unspecified modulo or decoding step to make sense of it as a 2D binning, and the product form is not the permutation-style hash used elsewhere. Third, the claim that ATSFFT always controls error better than SFFT is contradicted by Table IV itself at N=2^12, k=100 and k=600, where SFFT's error is lower. Minor, but the text overstates. Fourth, no code and no error bars.\n\nOne correction to the stress test: the alleged contradiction between Algorithm 2 and Eq. 12 is not there. Both halve B when the ratio is close to 1, keep it for intermediate changes, and double it when the ratio moves a lot. They agree.\n\nWho is this for? Readers who want a benchmark-oriented view of a sparsity-estimating SFFT variant, and referees who want to test whether the local-max counting heuristic can be made rigorous. As a claimed novel algorithm, it is not there yet.\n\nIf this crossed my desk, I would send it to peer review — the problem matters and the claims are testable — but I would expect referees to demand a real proof or a careful empirical characterization of the local-max identity, and a hash function that actually maps to a 2D grid. The authors' own 2017 papers should also be acknowledged as the source of the core mechanism.","headline":"The sparsity-detection claim is supported by one example and the Eq. 8 hash is mis-specified; the paper is an extended experimental version of the authors' 2017 work, not a new algorithm.","tokens_in":12424,"tokens_out":10201,"would_cite":false,"duration_ms":100147,"reading_group":"maybe","serious_thinker":"unclear","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive tuning lets a two-dimensional sparse Fourier transform estimate its own sparsity k by counting local maxima in a hashed grid, then finish the transform without knowing k in advance.","keywords":["sparse fast Fourier transform","sparsity detection","adaptive tuning","two-dimensional DFT","image sparsity","hash function","local maximum","FFTW"],"falsifier":"Take a synthetic $N \\times N$ image with known sparsity $k$, choose the nonzero frequency coordinates randomly, run the hash function for many trials, and count local maxima in the resulting $B \\times B$ matrix; if any trial yields a count different from $k$, the central equality asserted in Section III.A is false. A targeted version places two nonzero coefficients so that, after permutation and filtering, their hash bins are adjacent and their filter spreads merge into a single local maximum.","tokens_in":11317,"feed_emoji":"⚡","tokens_out":6893,"duration_ms":65283,"temperature":0.7,"pith_summary":"The paper proposes ATSFFT, a two-dimensional sparse fast Fourier transform that removes the usual requirement that the user supply the signal sparsity $k$. Its method hashes the frequency grid down to a small $B \\times B$ matrix and counts local maxima, which it asserts equals the number of nonzero frequency coefficients. An adaptive loop adjusts $B$ until successive counts of $k$ stabilize, then runs the standard seek-location and estimate-coefficient stages. This would make sparse Fourier transforms practical for image inputs whose sparsity is unknown in advance, which is the common real-world situation. Experiments report that ATSFFT runs faster than the prior sparse FFT and about an order of magnitude faster than the FFTW library while keeping the reported error lower.","feed_headline":"Sparse FFT learns its own sparsity and beats FFTW by 10x","feed_subtitle":"Counting local maxima in a hashed grid estimates k on the fly, removing the main obstacle to using sparse FFT on images.","key_machinery":"The load-bearing object is the two-dimensional hash function $h_{\\sigma_1,\\sigma_2}(i,j) = \\mathrm{round}(\\sigma_1 \\sigma_2 i j B^2/N^2)$, assembled from random spectrum permutation, a two-dimensional flat Gaussian window filter, and fast subsampling with an FFT of size $B \\times B$. This hash maps $N \\times N$ frequency coordinates into $B \\times B$ bins and is supposed to concentrate the image's nonzero coefficients into exactly $k$ local maxima, making sparsity observable. The adaptive controller built on that count, the update rules in Eq. (12), is what distinguishes ATSFFT from a standard sparse FFT: instead of taking $k$ as an input and fixing $B = \\sqrt{Nk}$, it tunes $B$ by powers of two until successive sparsity estimates agree. The reverse-hash and median-based coefficient estimation stages then convert the stabilized bin information into explicit coordinates and amplitudes.","core_discovery":"The paper's central discovery is that unknown sparsity can be probed rather than assumed: after the hash function, the number of local maxima in the hashed $B \\times B$ magnitude matrix is asserted to be the same as the image's sparsity $k$. Starting from an initial small $B_0$, the algorithm counts local maxima to obtain $k_1$, defines the change ratio $r_i = |1 - k_i/k_{i-1}|$, and updates the bin size by $B_{i+1}=B_i/2$ when $r_i < 2\\%$, $B_{i+1}=B_i$ when $2\\% \\le r_i < 5\\%$, and $B_{i+1}=2B_i$ when $r_i \\ge 5\\%$. Once $B$ and $k$ stabilize, candidate coordinates are collected by reverse hashing from locations that appear in at least half of the seek loops, and each coefficient is taken as the median of repeated estimation rounds. The paper reports that this self-tuning procedure runs faster than both the original sparse FFT and FFTW, with smaller average L1 error on the tested sparse images.","pith_inferences":["If local-maximum counting is only reliable when the random permutation spreads nonzero coefficients far apart, then the correctness of the sparsity probe is probabilistic; a reader should expect a formal bound on the chance that two nonzeros merge into one peak, but the paper does not supply one.","The hash in Eq. (8) maps a 2D coordinate to a single rounded integer rather than a pair of bin indices; a testable extension would compare this scheme with separable row and column hashing to see which gives more stable local-maximum counts.","The update thresholds 2% and 5% are fixed constants; they could be tuned per signal class or made to depend on $N$ and $B$, and the paper leaves that margin unexamined.","Because the equality between local maxima and $k$ is demonstrated with a single example, a natural next step is to measure the failure rate of that equality over random coefficient placements and window parameters."],"forward_implications":["Users no longer need to know or guess the sparsity $k$ before running the transform, so sparse FFT can be applied where signals are only known to be sparse in the frequency domain.","Because $B$ adapts to the signal rather than being fixed by an assumed $k$, runtime stays low as sparsity varies; reported runtimes for $N=2^{11}$ and $N=2^{12}$ remain under 0.1 seconds across $k$ from 50 to 1000.","The method extends the range where sparse FFT beats FFTW: at $N=2^{12}$ and $k=1000$, the earlier sparse FFT is slower than FFTW while ATSFFT remains faster.","Reported error decreases as image size grows for fixed sparsity, meaning the method becomes more accurate precisely in the large-image regime where its speed advantage is largest."],"supporting_citations":[{"why":"Supplies the original practical sparse Fourier transform algorithm that ATSFFT adapts to two dimensions.","marker":"[15]"},{"why":"Supplies the nearly-optimal sparse Fourier transform construction that motivates replacing full FFT by hashing and location loops.","marker":"[16]"},{"why":"Earlier two-dimensional sparse Fourier transform algorithm whose hash, seek, and estimate workflow ATSFFT extends.","marker":"[17]"},{"why":"Earlier adaptive tuning sparse Fourier transform; the current paper revises and extends its sparsity-probing idea.","marker":"[18]"},{"why":"FFTW is the state-of-the-art FFT library used as the performance baseline for runtime and speedup comparisons.","marker":"[19]"}],"fun_headline_variants":["Auto-tuning sparse FFT finds sparsity, beats FFTW","Sparse FFT that counts peaks to estimate k, outruns FFTW","Adaptive SFFT learns k, delivers 10x over FFTW","No sparsity guess needed: self-tuning SFFT beats FFTW","Adaptive sparse FFT solves unknown sparsity, outperforms FFTW"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole sparsity-detection mechanism rests on the assertion that after hashing, the number of local maxima in the $B \\times B$ matrix equals the true sparsity $k$; if that count is off, the adaptive loop estimates the wrong $k$ and the update rules for $B$ have no justification.","fun_headline_variants_meta":{"raw":{"variants":["Auto-tuning sparse FFT finds sparsity, beats FFTW","Sparse FFT that counts peaks to estimate k, outruns FFTW","Adaptive SFFT learns k, delivers 10x over FFTW","No sparsity guess needed: self-tuning SFFT beats FFTW","Adaptive sparse FFT solves unknown sparsity, outperforms FFTW"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000704,"raw_usage":{"total_tokens":3224,"prompt_tokens":1042,"completion_tokens":2182,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":658,"completion_tokens_details":{"reasoning_tokens":2080}},"tokens_in":658,"tokens_out":2182,"duration_ms":17699,"temperature":1.0,"reasoning_tokens":2080,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:42:56.495233+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a synthetic $N \\times N$ image with known sparsity $k$, choose the nonzero frequency coordinates randomly, run the hash function for many trials, and count local maxima in the resulting $B \\times B$ matrix; if any trial yields a count different from $k$, the central equality asserted in Section III.A is false. A targeted version places two nonzero coefficients so that, after permutation and filtering, their hash bins are adjacent and their filter spreads merge into a single local maximum.","supporting_citations":[{"cited_title":"1183–1194","cited_arxiv_id":null,"evidence_quote":"Supplies the original practical sparse Fourier transform algorithm that ATSFFT adapts to two dimensions."},{"cited_title":"563–5 78","cited_arxiv_id":null,"evidence_quote":"Supplies the nearly-optimal sparse Fourier transform construction that motivates replacing full FFT by hashing and location loops."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier two-dimensional sparse Fourier transform algorithm whose hash, seek, and estimate workflow ATSFFT extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier adaptive tuning sparse Fourier transform; the current paper revises and extends its sparsity-probing idea."},{"cited_title":"Frigo and S","cited_arxiv_id":null,"evidence_quote":"FFTW is the state-of-the-art FFT library used as the performance baseline for runtime and speedup comparisons."}],"review_version":1}