{"id":"8b9781df-4555-41a6-ac82-6b31434055b6","arxiv_id":"2511.17239","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Gradient-MUSIC solves low-rank Toeplitz approximation and Fourier subspace estimation at minimax-optimal accuracy, with error bounds scaling as C√r‖E‖₂ and C√(r/n)‖z‖₂ respectively.","lead":"This paper proves that one spectral-estimation algorithm, Gradient-MUSIC, can be repurposed to optimally recover low-rank Toeplitz/Hankel matrices and Fourier subspaces from corrupted data. A generalist might read it because it turns two previously heuristic structured-approximation problems into provably minimax-optimal, efficient algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.1's 'rank exactly r' output guarantee is not established by the proof: the amplitude perturbation bound scales as √r, so a fixed absolute α cannot prevent zero amplitudes for arbitrarily large r.","rationale":"The reader's weakest assumption is the minimum-separation/conditioning condition, which the paper explicitly acknowledges and which is necessary for the well-conditioning of the Fourier matrices. My concern is different: Theorem 3.1 also promises the output has rank exactly r, and the proof does not guarantee this for all r with an absolute α. This is load-bearing because the abstract and theorem both emphasize 'rank exactly r'; if the rank drops, the algorithm does not solve the stated structured approximation problem. The concern is internal to the proof: inequality (3.10) yields ∥â−a∥∞ ≲ α√r, so for any fixed α, sufficiently large r makes the bound exceed the amplitude magnitude 1, and an adversarial E of norm ≤ αn can force a zero amplitude. The proof never shows â_j ≠ 0. This is a concrete gap, fixable by making α depend on r (α ≲ 1/√r) or by proving a sharper entrywise amplitude bound. It does not overturn the transference principle or the error-rate upper bounds for moderate r, but it does restrict the scope of the 'rank exactly r' claim. The reader's verdict of CONDITIONAL remains appropriate, but for a different reason than the one cited.","tokens_in":17817,"tokens_out":35292,"duration_ms":298553,"concrete_test":"Analytically, use the first-order expansion â ≈ a − Φ⁺ Δ D − D Δ* Φ⁺* (with Δ = Φ̂−Φ) to compute the sensitivity of each â_j to E; show the operator norm from E (bounded by αn) to the diagonal entries is ≳ √r/n, so for r > 1/α² there exists an admissible E that zeros one entry. Numerically, fix n=6000, r=1500 (so r ≤ n/4 allows Δ≥8π/n), choose T ∈ T(n,r) with |a_j|=1 and min-separated frequencies, and for α=0.01, 0.1 run Gradient-MUSIC with an E optimized (e.g., via a few gradient steps) to minimize min_j |â_j|. If min_j |â_j| = 0 or the output rank is < r, the theorem's 'rank exactly r' assertion fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim includes the guarantee that the Gradient-MUSIC Toeplitz estimator outputs a Toeplitz matrix of rank exactly r. The estimator is T̂ = Φ̂ diag(â) Φ̂*, whose rank equals the number of nonzero entries of â (since Φ̂ has full column rank). The proof bounds ∥â−a∥∞ ≲ √r n∥x̂−x∥∞ + ∥E∥₂/n (Eq. 3.10), which with (3.8) and ∥E∥₂ ≤ αn gives ∥â−a∥∞ ≲ α√r. Because |a_j| ≥ 1, preserving rank r requires α√r ≤ c < 1. But the theorem declares α an absolute constant valid for all n≥100 and all r<n. For any fixed α, taking r > 1/α² makes the amplitude error bound exceed 1, and a worst-case E (whose norm is only O(n/√r)) can drive some â_j to zero, so rank falls below r. The proof does not address this, and the claim 'rank exactly r' is therefore not established for large r; the theorem as stated is likely false in that regime. This is distinct from the acknowledged separation condition and is an internal gap in the main result.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two structured approximation problems: recovering a low-rank Toeplitz matrix T from a noisy observation T+E, and recovering the Fourier subspace range(Φ(n,x)) from a single noisy vector Φ(n,x)a+z. The proposed algorithms first compute a leading singular subspace, feed it to the authors' Gradient-MUSIC spectral-estimation method, and then form a Toeplitz matrix or a Fourier subspace from the estimated frequencies. The main theorems (3.1 and 4.2) give error bounds of order √r∥E∥₂ and √(r/n)∥z∥₂ under separation and small-noise assumptions, and Theorems 3.2 and 4.3 give lower bounds showing optimality in n and in the noise level. The paper also contains complexity estimates and numerical experiments comparing the Toeplitz estimator with alternating projection.","tokens_in":18105,"tokens_out":18127,"duration_ms":164371,"significance":"The transference principle — using a spectral-estimation algorithm as a black box for structured matrix and subspace recovery — is conceptually attractive and, if the technical gaps are fixed, would provide the first provably minimax-optimal polynomial-time methods for these two problems. The algorithms are deterministic, have explicit complexity bounds, and the authors provide reproducible code. The reliance on the authors' prior Gradient-MUSIC analysis [12] is heavy, but that prior work is stated to contain parameter-free, assumption-explicit proofs. The main risk is the exact-rank guarantee in Theorem 3.1, which is not established by the given argument.","major_comments":[{"comment":"The 'rank exactly r' guarantee is not supported. The estimator is T̂ = Φ̂ diag(â) Φ̂*, so its rank equals the number of nonzero entries of â (Φ̂ has full column rank). The proof obtains ∥â−a∥∞ ≲ √r∥E∥₂/n (Eq. (3.10)), which under ∥E∥₂≤αn is ≤ Cα√r. Since |a_j|≥1, one can conclude â_j≠0 only if Cα√r<1. But α is declared absolute while r is allowed to be arbitrarily large (r<n), so for r > (Cα)^{-2} the argument fails; an adversarial E satisfying the norm bound can in principle zero out an amplitude. The sentence 'This is clearly a Toeplitz matrix of rank exactly r' is therefore unjustified. This gap propagates to Corollary 3.3 and the abstract's exact-rank claim. The theorem must be restated with an explicit r-dependent smallness condition, or the proof must provide a different mechanism for preserving the rank.","section":"Sec. 3.2, Theorem 3.1"},{"comment":"The reduction from spectral estimation to Toeplitz recovery is not fully specified. The observation is written as y=Φ(2n−1,x)a+z with the paper's convention that Fourier matrices have rows j=0,...,2n−2, but the Toeplitz matrix T(y) needs entries t_m for m=−(n−1),...,n−1. It is not explained how the negative-index entries are obtained from y. If a symmetric index set is intended, this must be stated explicitly and the spectral-estimation lower bound (Lemma 2.2) must be applied to that convention. As written, the equality T(y)=Φ(n,x)diag(a)Φ(n,x)^*+T(z) is not demonstrated.","section":"Sec. 3.3, proof of Theorem 3.2"}],"minor_comments":[{"comment":"The first abstract says 'three structured approximation problems' and gives the Toeplitz bound as C∥E∥₂ without √r, while the full-text abstract and Theorem 3.1 state two problems and give C√r∥E∥₂. Please align these statements.","section":"Abstract / title"},{"comment":"The statement says the estimator outputs a Fourier subspace bU ⊆ C^n of dimension n; it should be dimension r.","section":"Sec. 4, Theorem 4.2"},{"comment":"The line 'Since C = 100' should read 'Since C = 1/100'; with C=1/100 the displayed inequality contradicts Lemma 2.2. Also, Corollary 4.4 uses F*(m,r,...) in the proof although the statement uses n.","section":"Sec. 4.3, proof of Theorem 4.3 and Corollary 4.4"},{"comment":"The paper motivates the noise condition ∥z∥₂≤α√(n/r) by noting that ∥z∥₂≤α√n is necessary, but does not know if the extra 1/√r is needed. This is fine, but the gap between the necessary and sufficient conditions should be highlighted in the discussion.","section":"Sec. 4.1"},{"comment":"The claim that r can be deduced by a thresholding procedure cites [12, Lemma 5.6] but the lemma is not stated. Since r is assumed known in the algorithm and theorems, the reader would benefit from a short statement of the thresholding guarantee.","section":"Sec. 3.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's main theorems depend on the authors' prior preprint [12] for Gradient-MUSIC, including the amplitude-error lemma. The committee may wish to verify that [12] is robust before accepting the transference results. The exact-rank issue in Theorem 3.1 is the main obstacle; it is fixable by adding an explicit condition such as α√r ≤ c or by adjusting the claim, but the current statement is too strong."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real contribution that deserves peer review, but the advertised \"rank exactly r\" output is the weakest point, and the stress-test note is correct. The proof of Theorem 3.1 bounds ||â−a||∞ ≲ √r ||E||₂/n ≤ Cα√r. Since |a_j|≥1, exact rank preservation requires that bound to be <1 for all E at the allowed noise level. For any fixed α, that fails once r ≳ 1/α², so for large r the constructed T̂ can drop below rank r. The error bound ||T−T̂||₂ ≤ C√r ||E||₂ may still hold, but the exact-rank claim as stated is not established. The authors would need either an extra post-processing step that forces zeroed amplitudes back to nonzero values (with a proof that this doesn't hurt the error) or a revised statement that only promises rank ≤ r.\n\nWhat is genuinely new: the Fourier subspace estimation problem (identifying range(Φ(n,x)) from one vector) appears to be new, and the transference principle that turns any spectral estimation algorithm with subspace-input guarantees into a Toeplitz/Hankel approximation method is a nice reusable template. The lower bounds via contradiction reductions to the spectral-estimation minimax rate are clean, and the numerical experiments, while limited, show the method is competitive with alternating projection and much cheaper. The paper is honest about the separation assumption and says relaxing it is a different problem.\n\nMain soft spots: (1) the exact-rank gap above; (2) the minimax-optimality claims are only in n and noise level, not in r — the lower bounds in Corollaries 3.3 and 4.4 are independent of r or decay as 1/√r, while upper bounds grow as √r. The full-text abstract says optimal in n and ||E||₂, but the arXiv abstract says optimal in r as well; that should be fixed. (3) The proof leans heavily on [12] for Gradient-MUSIC's convergence, amplitude-error lemma, and rank-detection; the constants are hidden in \"sufficiently small α\" and ≲. For a journal version that is acceptable if [12] is published or the lemmas are restated, but right now a referee cannot fully verify Theorem 3.1 without digging into a preprint. Minor: the intro says \"dimension n\" where it should be \"dimension r.\"\n\nWho should read it: signal processing and approximation theory people working on low-rank Toeplitz/Hankel recovery and spectral estimation. It would be useful in a reading group.\n\nRecommendation: send it to peer review. The central errors are fixable and the transference principle is worth refereeing seriously.","headline":"Genuinely useful transference principle, but Theorem 3.1's exact-rank guarantee is not actually proved and the r-dependence in the optimality claims is loose.","tokens_in":18626,"tokens_out":4014,"would_cite":true,"duration_ms":36907,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A29","15B05","65F55"],"pacs":[],"model":"deepseek-v4-flash","headline":"One spectral-estimation algorithm, Gradient-MUSIC, solves Toeplitz matrix recovery, Fourier subspace estimation, and exponential-sum recovery at provably optimal rates, via a quantitative transference principle.","keywords":["Gradient-MUSIC","Toeplitz matrix approximation","Fourier subspace estimation","spectral estimation","exponential sums","minimax optimality","Hankel matrices","super-resolution"],"falsifier":"Construct a rank-2 Toeplitz matrix whose underlying frequencies are separated by less than 8π/n, add noise with ||E||₂ = αn for the α used in Theorem 3.1, and measure whether the output error exceeds C√r||E||₂; if it does, the conditioning premise fails. Alternatively, exhibit a method that on the full parameter class T(n,r) achieves an error strictly below the lower bound of Theorem 3.2, which would disprove the minimax claim.","tokens_in":17651,"feed_emoji":"📡","tokens_out":5153,"duration_ms":41541,"temperature":0.7,"pith_summary":"This paper argues that three problems usually treated separately—recovering the frequencies of an exponential sum, approximating a noisy low-rank Toeplitz matrix, and recovering a Fourier subspace from a single snapshot—are the same problem in disguise. The authors show that one spectral-estimation algorithm, Gradient-MUSIC, can be used as a black box for all three, and that the resulting estimators match the information-theoretic lower bounds. For Toeplitz matrices the guarantee is ||T − T̂||₂ ≤ C√r||E||₂ under noise ||E||₂ ≤ αn, with no dependence on n except through the noise; for Fourier subspaces the guarantee is ||sin(U, Û)||_F ≤ C√(r/n)||z||₂. A sympathetic reader would care because these rates are provably the best any method can achieve, and the algorithms are computationally light—essentially the cost of one truncated SVD plus a gradient search.","feed_headline":"One algorithm provably hits the optimal Toeplitz recovery rate","feed_subtitle":"The same estimator matches minimax bounds for Fourier-subspace and exponential-sum recovery.","key_machinery":"The load-bearing object is a Fourier matrix Φ(n,x) with rows indexed by integer times 0,...,n−1 and columns e^{ijx_k}; a separated frequency set x with Δ(x) ≥ 8π/n (or 16π/n) makes Φ well-conditioned via the large-sieve bound (2.2). Gradient-MUSIC is the subroutine: it forms a MUSIC-type objective on an input subspace and locates local minima by gradient descent, with the guarantee that a subspace perturbation of size δ leads to a frequency error at most 10δ/n. The transference principle is the chain of inequalities that turns frequency error into matrix or subspace error, and the lower-bound proofs that turn any too-good structured approximator into a too-good spectral estimator.","core_discovery":"The central claim is that the structured-approximation problems reduce, through a quantitative transference principle, to spectral estimation, and that Gradient-MUSIC—an algorithm that takes an arbitrary subspace close to a Fourier subspace and returns the underlying frequencies—carries the optimal error rates across all three. Theorem 3.1 states that for a rank-r Toeplitz matrix T with a well-conditioned Fourier factorization, corrupted by arbitrary noise E with ||E||₂ ≤ αn, the estimator outputs a Toeplitz matrix of rank exactly r with spectral-norm error at most C√r||E||₂ and Frobenius error at most Cr||E||₂; Corollary 3.3 proves a matching minimax lower bound, so the rate is optimal in n","pith_inferences":["Beyond the stated results, the transference principle suggests that any spectral-estimation method with a subspace-input guarantee and a matching lower bound would also yield optimal Toeplitz and Fourier-subspace estimators; Gradient-MUSIC is one instantiation, not the only possible one.","The authors leave open whether the extra 1/√r factor in the noise assumption for Fourier subspace estimation is necessary; removing it would extend the guarantee to higher-rank settings.","Because the truncated SVD already achieves minimax optimality as a preprocessing step, one testable extension is to plug the same pipeline into other structured families whose leading eigenspaces are parameterized by a small set of continuous parameters.","A natural next problem is the converse of the transference: whether an optimal Toeplitz or subspace estimator can be converted back into an optimal spectral estimator, which the paper does not answer."],"forward_implications":["Low-rank Toeplitz approximation is solved at minimax-optimal accuracy: for the parameter class T(n,r), no method can beat the C√r||E||₂ rate in n and noise.","Fourier subspace recovery from a single noisy snapshot has the same optimality: error at most C√(r/n)||z||₂, with a matching minimax lower bound.","The returned Toeplitz matrix always has rank exactly r, unlike alternating-projection or sparse-Fourier methods that can overestimate the rank.","A quantitative transference principle converts guarantees for spectral estimation into guarantees for the other two problems, so all three share the same noise-versus-dimension trade-offs.","The estimator runs in O(n²r + nr² log(n/||E||₂)) time, roughly one truncated SVD plus a gradient-descent search."],"fun_headline_variants":["One algorithm achieves minimax optimal rates for three structured recovery problems","Gradient-MUSIC solves three approximation problems at optimal rates","One estimator hits minimax bounds for Fourier, Toeplitz, and exponential sums","The same algorithm provably achieves optimal recovery for all three problems","Minimax-optimal recovery of Toeplitz, Fourier subspaces, and exponential sums"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire framework depends on the frequencies being sufficiently separated (at least 8π/n or 16π/n) so that the Fourier matrix is well-conditioned; if frequencies cluster, the conditioning bound fails and the error guarantees collapse.","fun_headline_variants_meta":{"raw":{"variants":["One algorithm achieves minimax optimal rates for three structured recovery problems","Gradient-MUSIC solves three approximation problems at optimal rates","One estimator hits minimax bounds for Fourier, Toeplitz, and exponential sums","The same algorithm provably achieves optimal recovery for all three problems","Minimax-optimal recovery of Toeplitz, Fourier subspaces, and exponential sums"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000645,"raw_usage":{"total_tokens":2838,"prompt_tokens":816,"completion_tokens":2022,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":560,"completion_tokens_details":{"reasoning_tokens":1924}},"tokens_in":560,"tokens_out":2022,"duration_ms":11801,"temperature":1.0,"reasoning_tokens":1924,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T20:55:52.650577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a rank-2 Toeplitz matrix whose underlying frequencies are separated by less than 8π/n, add noise with ||E||₂ = αn for the α used in Theorem 3.1, and measure whether the output error exceeds C√r||E||₂; if it does, the conditioning premise fails. Alternatively, exhibit a method that on the full parameter class T(n,r) achieves an error strictly below the lower bound of Theorem 3.2, which would disprove the minimax claim.","supporting_citations":[],"review_version":1}