{"id":"a4134392-68d5-41ea-b180-2b18e9f3cfb4","arxiv_id":"1908.04412","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new l1-minimization approach augments the measurement system with a random noise collector matrix, achieving zero false discoveries at any noise level without estimating the noise.","lead":"This paper introduces the Noise Collector, an extra matrix added to a sparse recovery problem that absorbs measurement noise without needing to know the noise level. The authors prove that, with high probability, the method finds no false signal detections at any noise level, and they demonstrate it on microwave array imaging.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The zero-FDR claim in the abstract is stated without the uniform-sphere condition on e/||e|| that Theorems 1–3 require; with anisotropic noise the method can provably produce false discoveries.","rationale":"I agree with the reader's identification of the uniform-sphere assumption as the weakest point. The theorem itself is conditional and may be correct; the problem is that the abstract and the phrase \"any level of noise\" suppress this condition. The failure mode is concrete (noise aligned with a dictionary atom), and the cost comparison uses the paper's own estimates (7)-(8), so this is not a matter of external consensus. Secondary issues—the circulant fast Noise Collector not being covered by the theorems, tau calibration, and the sketchiness of the proofs—reinforce the conditional verdict but are less central. The proposed test would settle whether the claim as communicated is too strong. Since the reader already marked the paper CONDITIONAL, my read does not change that verdict.","tokens_in":11630,"tokens_out":14740,"duration_ms":195166,"concrete_test":"Set up the Theorem 1 setting with, e.g., N = 625, K = 2000, Sigma = N^1.5, and C drawn with i.i.d. uniform columns on S^{N-1}. For b0 = 0 and e = a_j for a randomly chosen dictionary atom a_j, solve (4) with tau = c0 sqrt(ln N) and check whether the j-th entry of rho_tau is nonzero. Repeat for 100 randomly chosen atoms a_j. If a false discovery appears in every trial, the uniform-direction hypothesis is doing the work, and the abstract's unconditional \"any level of noise\" phrasing is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central guarantee depends entirely on the assumption, stated before Theorem 1 and used in its proof, that e/||e|| is uniformly distributed on S^{N-1}. The rotational-invariance step (\"the distribution of Phi_C(e) is rotationally invariant... thus n = z/||z|| is uniformly distributed\") is the only place where the probability bound (22) is obtained, and Theorems 2 and 3 inherit this assumption. The abstract, however, promises \"zero false discovery rate for any level of noise\" with no distributional caveat. The assumption is not merely technical: if e = a_j for a dictionary column a_j, then representing e with C costs at least ||eta_{a_j}||_1 > sqrt(N)/(c0 sqrt(ln N)) by estimate (8), while representing it with rho_j costs tau = c0 sqrt(ln N). For large N the first cost dominates, so the l1 minimizer sets rho_j = 1 and eta = 0, producing a false discovery. Hence the zero-FDR claim cannot hold for arbitrary noise; it is a statement about rotationally invariant noise. The paper should either scope the abstract and application claims to isotropic noise or extend the proofs to anisotropic noise.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for sparse recovery from noisy measurements by augmenting the dictionary A with a randomly constructed Noise Collector matrix C and solving the weighted l1-minimization problem (4), with weight tau = c0 sqrt(ln N) on the signal coefficients. The authors claim that, with high probability as N grows, the solution has zero false discovery rate for any level of noise, that exact support recovery occurs when the noise is not too large, and that a circulant-based Fast Noise Collector Algorithm achieves this at computational cost comparable to the original problem. Numerical experiments on passive array imaging illustrate the claimed behavior. The theoretical results are stated as Theorems 1-3, with proofs sketched in a final section.","tokens_in":11935,"tokens_out":8631,"duration_ms":87202,"significance":"If the central claim were correct as stated, the paper would make a valuable practical contribution: false-discovery control in high-dimensional sparse recovery without estimating the noise level is a genuinely useful property. The idea of introducing a random dictionary dedicated to absorbing noise is elegant, and Lemma 1, which quantifies the incoherence of the augmented system and the covering property of the noise collector, is a sound starting point. The numerical imaging results are suggestive. However, the paper's central claims currently outrun its proofs: the zero-FDR statement is made for arbitrary noise while the theorems require isotropy, the fast circulant construction is not covered by the theory, and a key proof step in Theorem 3 is an unjustified reduction. These issues are load-bearing and need to be resolved or the claims weakened before the paper can be accepted.","major_comments":[{"comment":"The abstract states that the l1-minimal solution of the augmented system has zero false discovery rate 'for any level of noise', but Theorem 1 assumes that e/||e|| is uniformly distributed on the unit sphere S^{N-1}. This assumption is essential, not technical. If e = a_j for a column of A, then by estimate (8) representing e with C costs at least sqrt(N)/(c0 sqrt(ln N)), while representing it with rho_j costs tau = c0 sqrt(ln N); for large N the l1 minimizer will set rho_j = 1 and eta = 0, producing a false discovery. Thus the zero-FDR claim fails for anisotropic or adversarial noise. The abstract and the application claims must be scoped to isotropic noise, or the theorems must be extended to non-isotropic noise.","section":"Abstract and Theorem 1"},{"comment":"The proof begins with 'It suffices to prove the result for 1-sparse rho' and then analyzes only rho = (1,0,...,0). This reduction is not justified. For an M-sparse signal, the constraint C eta = e + a_1(1-rho_1) is replaced by a sum over the support, and the l1 cost of the coupled system does not decouple linearly. The paper does not show that control of a single coefficient implies control of all M coefficients simultaneously. Without a rigorous reduction, exact support recovery for M>1 is not established by the given argument.","section":"Proof of Theorem 3"},{"comment":"The fast algorithm uses a circulant construction: N^{beta-1} random generating vectors are drawn and each is used to form an N x N circulant matrix, so the columns of C are cyclic shifts of one another. Lemma 1 and Theorems 1-3, by contrast, assume that the Sigma = N^beta columns of C are drawn independently and uniformly on S^{N-1}. The columns of a circulant matrix are highly dependent, so the probabilistic estimates (6) and (7) do not apply to the implemented C. The paper does not provide any theorem or argument covering the circulant construction; the numerical experiments therefore demonstrate a heuristic algorithm, not the object analyzed in the theory.","section":"Fast Noise Collector Algorithm"},{"comment":"The abstract and the 'Main Results' section claim that the method has no tuning parameters and does not require parameter estimation, but the paper later states: 'For optimal results, one can calibrate c0 to be the smallest constant such that Theorem 1 holds, that is, we see no phantom signals when the algorithm is fed with pure noise.' This is a data-dependent calibration of a free parameter, explicitly tuned to the null distribution of the noise. This contradicts the no-parameter-estimation claim. Either a universal choice of c0 must be proven sufficient, or the claim must be softened to say that the method avoids estimating the noise level, not that it is parameter-free.","section":"Fast Noise Collector Algorithm and 'no tuning parameters' claim"},{"comment":"The proof of support inclusion for general A does not fully construct a dual certificate for the augmented problem with b0 != 0. It reuses the certificate z from the pure-noise map Phi_C(e) and bounds <a_i^v,z>, but the optimality conditions for (4) with signal present require a certificate that simultaneously controls the A- and C-columns for the actual solution with nonzero rho. The sentence 'Applying the previous arguments to z_w... we conclude rho_w_tau = 0' is only a sketch, and the decomposition step assumes bounds on <a_k,z> for support columns that have not been established for the signal-present problem. Theorem 2 needs a rigorous certificate argument before the zero-FDR claim is supported.","section":"Proof of Theorem 2"}],"minor_comments":[{"comment":"The proof states 'we assume that both c_i and -c_i are in C' and then works with the convex hull H. The theorem statement and the algorithm do not construct antipodal pairs; the reduction to a symmetric convex hull should be stated explicitly, since for real-valued eta the feasible set is the symmetric convex hull of the columns, but this equivalence is not discussed.","section":"Proof of Theorem 1"},{"comment":"In the proof of part (ii), the constant alpha is required to satisfy alpha < 4 sqrt(2 pi)/4 in one line, but the text does not explain the numerical value or the role of the factor; the choice of N sets of distinct indices and the resulting probability bound should be made more precise.","section":"Proof of Lemma 1"},{"comment":"Equation (22) contains the phrase 'for all i = j,...,K', which appears to be a typo for 'for all j = 1,...,K'. The notation should be corrected.","section":"Proof of Theorem 1"},{"comment":"In Figure 4 the caption describes tau = 2 as 'the correct tau' in (14). Since the theory allows any tau = c0 sqrt(ln N) with sufficiently large c0, the word 'correct' is misleading without specifying the calibration criterion used.","section":"Figures and captions"},{"comment":"The footnote says the results hold for complex data, but the proofs and optimization statements are written for real variables. A short justification or reference for the complex case would improve clarity.","section":"Complex data"}],"recommendation":"major_revision","confidential_remarks":"The main risk is that all numerical experiments use the circulant noise collector, whose theoretical status is open, and the calibration of c0 is data-dependent. I would ask the authors to either prove the needed properties for the circulant construction, or clearly separate the theoretical results from the algorithm used in practice. The abstract should be scoped to isotropic noise unless the anisotropic case is addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The Noise Collector idea is worth taking seriously. The paper improves on the authors' earlier version by showing that a polynomial number of noise dictionary columns suffices, and it introduces the tau weight that makes noise absorption cheap. That is a real theoretical step, and the passive array imaging experiments look good: at SNR=1 the method cleans up the image and finds the true support, which is more than standard l1 does.\n\nThe geometric argument is appealing, and the fast circulant implementation is a practical bonus. If the guarantee held as advertised, this would be a genuinely useful tool.\n\nBut the abstract overstates what is proved. The zero-false-discovery theorem is not for 'any level of noise' in the sense most readers will take it; it requires e/||e|| uniformly distributed on the sphere. The stress-test point is correct: if e is aligned with a dictionary column, representing e via C costs more than representing it via A, so the l1 minimizer will create a false discovery. That is not an exotic case. The proofs are also sketches: the reduction to 1-sparse signals in Theorem 3 is asserted, and the rotational invariance of the dual certificate in Theorem 1 needs a real argument. The fast algorithm uses a circulant C that is not the random uniform-sphere model of the theorems. And the claim of no tuning parameters is softened by the suggested calibration of c0 against pure noise.\n\nNone of these are fatal to the core idea, but they mean the paper is not yet as clean as its abstract suggests. A serious referee could push the authors to clarify the noise model, tighten the proofs, and state what the algorithm actually guarantees. I would send it out, with a request for revisions rather than a desk rejection.","headline":"A promising idea for tuning-free sparse recovery, but the headline zero-FDR claim outruns the proofs, which only cover rotationally invariant noise.","tokens_in":12435,"tokens_out":2036,"would_cite":false,"duration_ms":21155,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62J07","90C25","94A12","60D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that adding a random Noise Collector matrix to l1 minimization yields zero false discovery rate for any noise level, with probability tending to one as the data dimension grows.","keywords":["noise collector","sparse recovery","l1 minimization","false discovery rate","support recovery","high-dimensional probability","array imaging","compressed sensing"],"falsifier":"Take $N=10^4$, build $A$ from random unit vectors, set $b_0=0$, and choose the noise vector $e$ to point exactly along a fixed column of $A$ (so $e/\\|e\\|$ is deterministic, not uniform on the sphere). Solve the augmented $\\ell^1$ problem with $\\tau = 0.8\\sqrt{\\ln N}$. Theorem 1 predicts $\\rho_\\tau = 0$ with high probability, but the isotropy assumption fails, so any nonzero recovered coefficient would falsify the claim that the zero-false-discovery rate holds for any noise.","tokens_in":11444,"feed_emoji":"🎯","tokens_out":4924,"duration_ms":45156,"temperature":0.7,"pith_summary":"The paper proposes a method for recovering sparse signals from noisy high-dimensional measurements without estimating the noise level. It augments the linear system with a Noise Collector matrix $C$ and solves an $\\ell^1$-minimization problem over the original signal and the noise, with a weight $\\tau$ proportional to $\\sqrt{\\ln N}$. The central claim is that this augmented problem has zero false discovery rate for any level of noise, with probability tending to one as the data dimension grows. If correct, sparse support detection becomes a parameter-free procedure, which matters for imaging and other applications where noise levels are hard to calibrate.","feed_headline":"Zero false discoveries in noisy sparse recovery","feed_subtitle":"An augmented l1 method removes noise without estimating its level, with high probability as data grows.","key_machinery":"The central object is the Noise Collector matrix $C$, an $N \\times \\Sigma$ matrix with $\\Sigma = N^\\beta$ ($\\beta>1$) columns drawn uniformly and independently on the unit sphere, arranged as circulant blocks so that multiplication by $C$ and $C^*$ can be done by FFT. The key mechanism is the dual-certificate bound: for a typical noise direction, the dual certificate $z$ of the optimal $(0,\\eta)$ solution is uniformly distributed on the sphere, so the probability that any column $a_j$ of $A$ aligns with $z$ beyond $\\tau$ is exponentially small; this forces $\\rho_\\tau$ to have no false discoveries. The geometric picture is that the $\\ell^1$ ball of radius $O(\\sqrt{N})$ intersects the unit sphere in a region of small area, so a random direction $e$ is almost surely explained by the noise collector rather than by the signal columns.","core_discovery":"On the paper's own terms, the central discovery is that adding a random Noise Collector matrix $C$ of polynomially many columns to the measurement system, and minimizing $\\tau\\|\\rho\\|_{\\ell^1} + \\|\\eta\\|_{\\ell^1}$ subject to $A\\rho + C\\eta = b_0 + e$, separates signal from noise purely by $\\ell^1$ geometry. The paper proves three theorems: (1) with pure noise ($b_0=0$), the recovered signal $\\rho_\\tau$ is zero with high probability; (2) with an $M$-sparse signal and incoherent columns of $A$, the support of $\\rho_\\tau$ is contained in the true support; and (3) if the noise-to-signal ratio is below $c_2/\\sqrt{\\ln N}$, the supports coincide exactly. The weight $\\tau$ is chosen on the order of $\\sqrt{\\ln N}$, and the noise collector columns are drawn uniformly on the unit sphere, making the construction parameter-free apart from universal constants.","pith_inferences":["If the isotropy assumption is relaxed, the zero-false-discovery claim likely degrades; anisotropic noise aligned with columns of $A$ could be mistaken for signal, so practical applications may need to whiten the noise first or check robustness empirically.","The phase transition shown in the paper's Figure 5 suggests the method tolerates sparsity up to a threshold; a possible extension is to derive a sharp phase-transition curve for the augmented system analogous to compressed sensing.","The same augmented approach could apply to matrix completion or robust PCA where noise is dense rather than sparse, provided a suitable incoherent 'noise dictionary' can be constructed.","For finite $N$, the probability bounds have constants depending on $\\kappa$ and $\\beta$; calibrating $\\tau$ by running the algorithm on pure noise (as the paper suggests) may be a practical alternative to the theoretical constant."],"forward_implications":["No parameter estimation is needed: the method does not require the noise level or a tuning parameter $\\lambda$; the weight $\\tau$ is set from universal constants and $N$ alone.","Zero false discovery rate holds for any noise level, so the true support can be detected even at SNR near 1, as demonstrated in passive array imaging with signal-to-noise ratio equal to 1.","When the noise is moderate ($\\|e\\|/\\|b_0\\| \\le c_2/\\sqrt{\\ln N}$), exact support recovery holds, so after support detection a classical $\\ell^2$ solve on the support gives full amplitude recovery.","The computational cost is comparable to solving the original $\\ell^1$ problem, because the circulant structure makes noise collector multiplications $O(N^\\beta \\log N)$ and only the generating vectors need to be stored."],"supporting_citations":[{"why":"Defines the basis pursuit $\\ell^1$ minimization that the augmented system extends.","marker":"[9]"},{"why":"Supplies the incoherence conditions used to ensure exact sparse recovery.","marker":"[11]"},{"why":"Provides the high-dimensional probability estimates for random vectors used throughout the proofs.","marker":"[30]"},{"why":"Prior work that introduced the Noise Collector idea and is extended here.","marker":"[20]"},{"why":"Earlier noise-dictionary approach that the paper contrasts with its dense-noise model.","marker":"[17]"},{"why":"The Lasso, the baseline method whose tuning-parameter dependence the Noise Collector avoids.","marker":"[26]"},{"why":"Provides conditions for support containment in noisy $\\ell^1$ recovery that the theorems refine.","marker":"[27]"},{"why":"The GeLMA iterative soft-thresholding algorithm used to solve the augmented variational problem.","marker":"[21]"},{"why":"The theory of circulant matrices that enables the fast FFT-based implementation.","marker":"[15]"}],"fun_headline_variants":["Noise Collector: zero false discoveries, no tuning","Sparse recovery without noise estimation via Noise Collector","Augmented l1 trick removes noise without knowing its level","Parameter-free method separates signal from noise in sparse recovery"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs require that the noise direction $e/\\|e\\|$ be uniformly distributed on the unit sphere, and that the noise collector columns also be drawn uniformly at random; if the noise is correlated or anisotropic, the zero-false-discovery guarantee has no support in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Noise Collector: zero false discoveries, no tuning","Sparse recovery without noise estimation via Noise Collector","Augmented l1 trick removes noise without knowing its level","Parameter-free method separates signal from noise in sparse recovery"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001049,"raw_usage":{"total_tokens":4414,"prompt_tokens":959,"completion_tokens":3455,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":3392}},"tokens_in":575,"tokens_out":3455,"duration_ms":23457,"temperature":1.0,"reasoning_tokens":3392,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:00:47.431993+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $N=10^4$, build $A$ from random unit vectors, set $b_0=0$, and choose the noise vector $e$ to point exactly along a fixed column of $A$ (so $e/\\|e\\|$ is deterministic, not uniform on the sphere). Solve the augmented $\\ell^1$ problem with $\\tau = 0.8\\sqrt{\\ln N}$. Theorem 1 predicts $\\rho_\\tau = 0$ with high probability, but the isotropy assumption fails, so any nonzero recovered coefficient would falsify the claim that the zero-false-discovery rate holds for any noise.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the basis pursuit $\\ell^1$ minimization that the augmented system extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the incoherence conditions used to ensure exact sparse recovery."},{"cited_title":"Vershynin, High-dimensional probability","cited_arxiv_id":null,"evidence_quote":"Provides the high-dimensional probability estimates for random vectors used throughout the proofs."},{"cited_title":"Moscoso, A","cited_arxiv_id":null,"evidence_quote":"Prior work that introduced the Noise Collector idea and is extended here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier noise-dictionary approach that the paper contrasts with its dense-noise model."},{"cited_title":"Tibshirani, Regression Shrinkage and Selection via the lasso, Journal of the Royal Statistical Society","cited_arxiv_id":null,"evidence_quote":"The Lasso, the baseline method whose tuning-parameter dependence the Noise Collector avoids."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides conditions for support containment in noisy $\\ell^1$ recovery that the theorems refine."},{"cited_title":"Moscoso, A","cited_arxiv_id":null,"evidence_quote":"The GeLMA iterative soft-thresholding algorithm used to solve the augmented variational problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The theory of circulant matrices that enables the fast FFT-based implementation."}],"review_version":1}