{"id":"e5225536-ecfa-42a3-8433-f6dbd98f82c9","arxiv_id":"1908.01249","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A discrete-grid Christoffel sampling strategy achieves near-optimal O(N log N) sample complexity for weighted least-squares approximation of multivariate functions on general domains.","lead":"This paper designs random sampling schemes for least-squares approximation of multivariate functions on irregular domains, using a fine grid and orthogonalization to build a near-optimal sampling measure. The authors prove that O(N log N) samples are enough for stable, accurate approximation, and test the methods on polynomial approximation in several non-rectangular domains.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The general-domain accuracy claim depends on a K-bound that is proven only for λ-rectangle domains; for balls, simplices and other irregular domains the required K is open, so the title overstates what is established.","rationale":"I read the paper in good faith: the core mathematical derivation is rigorous, the concentration arguments are standard and correctly applied, and the authors are transparent about the K-grid limitation, explicitly calling the general-domain Nikolskii problem open in Remark 3.7 and §6. The reader's CONDITIONAL verdict is therefore appropriate. My partial disagreement concerns the precise wording of the weakest assumption. Theorem 2.1 is, in fact, a valid statement for every domain and every finite-dimensional P, provided one treats N(P,ρ) as a possibly unknown but finite constant; the theorem is not restricted to the grid or to λ-rectangle domains. What is missing is a quantitative, computable bound on K for non-λ-rectangle domains and for spaces such as hyperbolic-cross polynomial spaces on balls or simplices. That distinction matters: the concern is not a flaw in the proof but an overstatement in the abstract's phrase 'on general domains' relative to the proven, constructive guarantees. The numerical experiment proposed would test whether the gap is merely a missing proof artifact or a genuine algorithmic failure on a representative excepted domain. If the D constant stays bounded at feasible K, the conditional verdict could later be upgraded; if D grows, the authors should qualify the 'general domains' claim in the abstract. For now, the reader's CONDITIONAL verdict remains the most defensible position, so I recommend no change.","tokens_in":18943,"tokens_out":24620,"duration_ms":264365,"concrete_test":"For the simplex domain Ω2={y: y1+y2≤1} in d=2 (a domain explicitly outside Proposition 3.6) and the hyperbolic-cross polynomial spaces used in §5, take N up to 1000 and several grid sizes K (e.g., 2·10^4, 10^5, 10^6). In the orthonormal basis with respect to τ, compute D exactly as D^2=λ_max(G), where Gij=∫ φi φj dρ, and compare with the target D≤1/√(1−δ). If D remains near 1 once K reaches a moderate multiple of N^2 log N, the missing Nikolskii bound is a proof gap rather than a failure; if D grows with N even at K≈10^6, then the paper's full-domain accuracy claim is not supported for one of its own example domains and the title-level generality is overstated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that M=O(N log N) samples from the Christoffel-weighted discrete grid yield a well-conditioned and accurate L2(Ω,ρ) approximation on general domains. The M-conditioning part (Theorem 3.3) is solid. The accuracy over Ω, however, is mediated by the constant D of (3.7), and the only sufficient condition supplied is Proposition 3.4: K ≥ N(P,ρ)^2 f(δ)^{-1} log(N/γ). An explicit bound on the Nikolskii constant N(P,ρ) is proven only for λ-rectangle domains with lower-set polynomial spaces and uniform ρ (Proposition 3.6). Remarks 3.7 and §6 concede that for balls, simplices, and other irregular domains the Nikolskii constant is open. Thus Theorem 2.1 guarantees L2(Ω,ρ) accuracy for a general domain only in the conditional sense 'if K is chosen with N(P,ρ) known'; it gives no way to select K for the very domains highlighted in the title. The numerical section does not close this gap: the domains in Fig. 1 (annulus, simplex, exterior of ball) are not covered by Proposition 3.6, and Fig. 4 shows that the K=20000 grids used can yield off-grid errors orders of magnitude worse than on-grid errors, consistent with D≫1. This is an acknowledged limitation rather than an internal inconsistency, but it is the load-bearing gap for the 'general domains' claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces two weighted least-squares sampling strategies for function approximation on a general domain Ω. The methods first construct a K-point grid, orthogonalize the supplied basis on this grid, and then draw M independent samples from a discrete Christoffel-weighted probability measure. The main theorems (Theorems 2.1 and 2.2) claim that M = O(N log N) samples suffice for the least-squares matrix to be well conditioned and for the L2(Ω,ρ) error to be bounded by a best-approximation term plus a weighted sup-norm term, provided K is chosen according to the Nikolskii constant of the approximation space. A second, adaptive version recycles samples when the approximation space is enlarged. Numerical experiments on annulus, simplex, and exterior-of-ball domains compare the new methods with uniform sampling.","tokens_in":19185,"tokens_out":16445,"duration_ms":147543,"significance":"The core technical contribution is sound and valuable: the construction of a discrete orthogonality measure from a coarse grid, together with a Christoffel-weighted sampling distribution, yields log-linear sample complexity M = O(N log N) for well-conditioned weighted least squares on irregular domains, improving on the quadratic bounds of earlier work. The proofs use a clean application of the Matrix Chernoff inequality and the cited Nikolskii estimates, and the methods are straightforward to implement. The main caveat is that the provable guarantee over the whole domain Ω depends on a grid-size bound K that is made explicit only for λ-rectangle domains; for balls, simplices, and other irregular domains the required K is left open, so the 'general domains' framing in the title and abstract is stronger than what is established.","major_comments":[{"comment":"The title, abstract, and Theorem 2.1 present the result as a provable accuracy guarantee on general domains, but the L2(Ω,ρ) error bound requires K to satisfy the condition involving N(P,ρ) in Theorem 2.1, and an explicit bound on N(P,ρ) is proven only for λ-rectangle domains with lower-set polynomial spaces and uniform ρ (Proposition 3.6). Remark 3.7 explicitly states that for balls and simplices, and more generally for irregular domains, the Nikolskii constant is unknown, and Section 6 repeats this limitation. The numerical examples in Fig. 1 include a simplex (Ω2) and an exterior-of-ball domain (Ω3) that are not covered by Proposition 3.6, and Fig. 4 shows that for K = 20000 the off-grid error can be orders of magnitude larger than the on-grid error. The abstract and Theorem 2.1 should be qualified to state that the whole-domain accuracy guarantee is conditional on a known/effective bound for N(P,ρ), or the authors should add explicit Nikolskii bounds for at least some non-λ-rectangle domains.","section":"Abstract, Theorem 2.1, Section 3.6"},{"comment":"In the statement of Theorem 2.1 and in its proof, the norm |||g|||_{Z,π} is defined as max_{i=1,...,K} |g(z_i)|√(Kπ_i). However, from (3.13) and (3.14), w(z_i) = 1/(Kπ_i), so √(w(z_i))|g(z_i)| = |g(z_i)|/√(Kπ_i), not |g(z_i)|√(Kπ_i). Thus the displayed identity in the proof of Theorem 2.1 and the definition in Theorem 2.1(iii) appear to be the reciprocal of the correct weighted sup-norm. If the formula as printed is intended, the bound in Theorem 2.1(iii) does not follow from Theorem 3.1; if it is a typographical omission of a division sign, it must be corrected. The same issue affects the definition of |||g|||_{Z,π,t} in Theorem 2.2.","section":"Theorems 2.1 and 2.2, proof of Theorem 2.1"}],"minor_comments":[{"comment":"The definitions of C and D use the condition p|supp(τ) ≠ 0 and p|supp(ρ) ≠ 0 to exclude a zero denominator, but the denominator is ‖p‖_{Υ,w} and ‖p‖_{L2(Ω,τ)}, respectively, and a function can be nonzero on the support while vanishing on the sample points or the grid. The intended condition is that the denominator be nonzero, or equivalently that the relevant semi-norm be a norm on P.","section":"Section 3.1, Eqs. (3.6) and (3.7)"},{"comment":"There are several typographical errors, including 'simplicies' in Remark 3.7 (should be 'simplices') and 'with resect to' in the proof of Theorem 4.1 (should be 'with respect to'). A careful copyedit is recommended.","section":"Throughout"},{"comment":"The text describing Fig. 3 refers to different scalings of M with N, but it is not clear from the caption or the text which curves correspond to M = cN versus M = cN log N. Please identify the scalings in the caption or legend.","section":"Section 5, Fig. 3"},{"comment":"The sentence stating that ∑|φ_i(y)|^2 is the reciprocal of the Christoffel function is correct but would be clearer if it noted that the Christoffel function itself is typically defined as the reciprocal of this sum.","section":"Section 2.1"}],"recommendation":"major_revision","confidential_remarks":"This is a solid paper whose core technical results are correct. The main weakness is the mismatch between the 'general domains' claim and the proven grid-size bounds. I would ask the authors to moderate the abstract and theorem statements, and to fix the norm-definition issue in Theorems 2.1 and 2.2; if the norm issue is a simple typo, the fix is local. The relationship to the simultaneous work of Migliorati [20] is properly acknowledged, and I see no concerns about novelty or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The real contribution is a clean way to make Cohen-Migliorati optimal sampling work on non-tensor domains: build a discrete orthogonality measure from a K-point grid, orthogonalize the frame basis by QR, and sample according to Christoffel weights. That removes the practical barrier (needing a known orthonormal basis with tensorial structure) that kept optimal-sampling theory on boxes. The main theorem, M = O(N log N) for conditioning and grid accuracy, is proved with a standard Matrix Chernoff argument and is sound. Methods 1 and 2 are clearly specified; the adaptive version recycles samples, which matters in practice.\n\nCredit where due: the numerical section is honest. Figure 4 deliberately shows that off-grid error can be much worse than on-grid error when K is too small, which is exactly what the theory predicts. They don't hide the limitation.\n\nThe soft spot is the one you flagged: the K-bound controlling the constant D is only available for lambda-rectangle domains. Balls and simplices are explicitly excluded, and the paper admits the general-domain K problem is open. So the title's 'general domains' overstates what is proved. The conditioning result (Theorem 3.3) is fully general; the accuracy-over-Omega part is conditional on having K large enough in a way that is not quantified except in the lambda-rectangle case. I read the paper as acknowledging this, so it's not a hidden flaw, and the central mathematical engine is not affected. But the abstract should be more careful.\n\nMinor points: no code or data, and the averages over 50 trials have no error bars. Novelty is tempered by Migliorati's simultaneous work, though the paper cites it honestly.\n\nBottom line: worthwhile paper, deserves a serious referee. The fix is mainly in the claims--state that the log-linear guarantee is for the grid and for the conditioning, and that whole-domain accuracy requires a K for which the current sufficient bound is narrower than the title suggests. I'd take it to the reading group and would cite it.","headline":"Solid extension of optimal-sampling ideas to non-tensor domains, but the 'general domains' accuracy claim outruns what the K-bound actually proves; worth a serious referee with a claims-tightening revision.","tokens_in":19720,"tokens_out":2072,"would_cite":true,"duration_ms":22565,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A10","41A63","65D05","65F20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that $M=\\mathcal{O}(N\\log N)$ independent random samples, drawn from a discrete Christoffel-weighted measure on a fine grid, suffice for well-conditioned and accurate weighted least-squares approximation in an arbitrary…","keywords":["weighted least squares","sample complexity","Christoffel function","irregular domains","polynomial approximation","adaptive sampling","log-linear scaling","Nikolskii constant"],"falsifier":"Fix a domain without the $\\lambda$-rectangle property, such as the unit ball or a simplex, take uniform $\\rho$ and a standard total-degree or hyperbolic-cross polynomial space, and set $K$ to the bound in Theorem 2.1 with fixed $\\gamma,\\delta$. Estimate $D=\\sup_{p\\in P}\\|p\\|_{L^2(\\Omega,\\rho)}/\\|p\\|_{L^2(\\Omega,\\tau)}$ over many independent $K$-grids: if for moderately large $N$ the ratio repeatedly exceeds $1/\\sqrt{1-\\delta}$ while the computable constant $C$ stays near $1$, then the whole-domain form of the theorem fails for such domains even though the grid-level guarantee holds.","tokens_in":18704,"feed_emoji":"📐","tokens_out":12219,"duration_ms":113087,"temperature":0.7,"pith_summary":"This paper tries to establish that a multivariate function on an irregular domain can be approximated by weighted least squares using only $M=\\mathcal{O}(N\\log N)$ independent random samples, where $N$ is the dimension of the approximation space $P$. The key step is to build a fine $K$-point grid over the domain, orthogonalize any given basis on that grid, and draw samples from a discrete measure whose weights are the reciprocal Christoffel function of $P$ restricted to the grid. Under the stated conditions on $M$ and $K$, the least-squares matrix is well conditioned, the grid samples produce an accurate fit, and the whole-domain error is bounded by a best-approximation term plus a weighted sup-norm term whenever the grid is dense enough to control the constant $D$. The significance is that this improves the quadratic sample complexity available for irregular domains to the near-optimal log-linear scaling, with an adaptive variant that reuses all samples as $P$ grows.","feed_headline":"N log N samples tame least squares on irregular domains","feed_subtitle":"Christoffel-weighted random samples make irregular-domain least squares accurate and stable near N log N samples.","key_machinery":"The load-bearing object is a discrete orthogonality measure $\\tau = \\frac{1}{K}\\sum_{i=1}^K \\delta_{z_i}$ supported on a random grid. A reduced QR decomposition of the evaluation matrix $B$ turns an arbitrary, possibly nonorthogonal, basis into an orthonormal one with respect to $\\tau$; the squared row norms of $Q$ define the sampling distribution $\\pi_i = \\frac{1}{N}\\sum_{j=1}^N |q_{ij}|^2$, the discrete reciprocal Christoffel function. Sampling from $\\pi$ makes the weighted Nikolskii constant exactly $\\sqrt{N}$, so the Matrix Chernoff inequality gives $C \\le 1/\\sqrt{1-\\delta}$ once $M \\gtrsim N\\log N$. A separate constant $D$, bounded through the Nikolskii constant $\\mathcal{N}(P,\\rho)$ and the grid size $K$, converts the grid-level guarantee into an error bound in the desired $L^2(\\Omega,\\rho)$ norm.","core_discovery":"On the paper's own terms, the central claim is Theorem 2.1. For a fixed approximation space $P$ of dimension $N$, let $\\mathcal{N}(P,\\rho)$ be the Nikolskii constant and suppose $M \\ge N \\log(4N/\\gamma)((1+\\delta)\\log(1+\\delta)-\\delta)^{-1}$ and $K \\ge (\\mathcal{N}(P,\\rho))^2 \\log(2N/\\gamma)((1-\\delta)\\log(1-\\delta)+\\delta)^{-1}$. Then with probability at least $1-\\gamma$, the grid-evaluation matrix $B$ is full rank, the least-squares matrix $A$ satisfies $\\kappa(A) \\le \\sqrt{(1+\\delta)/(1-\\delta)}$, and for every $f \\in L^\\infty(\\Omega)$ the approximation $\\tilde f$ satisfies $\\|f-\\tilde f\\|_{L^2(\\Omega,\\rho)} \\le \\inf_{p\\in P}\\{\\|f-p\\|_{L^2(\\Omega,\\rho)} + (1-\\delta)^{-1} \\|f-p\\|_{Z,\\pi}\\}$. The adaptive Method 2 has the same guarantee for every space in a nested sequence (Theorem 2.2). The grid-level part of the guarantee holds without extra assumptions; the whole-domain part requires the grid to be dense enough that $D \\le 1/\\sqrt{1-\\delta}$, a condition proven for $\\lambda$-rectangle domains and left open for balls, simplices, and general irregular domains.","pith_inferences":["A Nikolskii or Christoffel bound for balls, simplices, or starlike domains would immediately convert the grid-level theorem into a whole-domain theorem, since the proof's only apparent gap is controlling $D$ for such domains.","The experiments suggest a practical adaptive-grid loop: monitor the computable constant $C$ on the current grid, and double $K$ until an independent off-grid error stops improving; the paper's experiments show exactly this improvement as $K$ doubles.","Because the sampling measure is discrete and supported on a user-chosen grid, the method should extend to settings where the domain is represented only by a point cloud or is learned from evaluations, provided the grid can still be generated from $\\rho$ in some form."],"forward_implications":["Uniform sampling on irregular domains requires at best quadratic sample complexity; the new sampling measure achieves the same accuracy and conditioning with $M=\\mathcal{O}(N\\log N)$, lowering the online least-squares cost from $\\mathcal{O}(N^4\\log N)$ to $\\mathcal{O}(N^3\\log N)$ for the spaces covered by the theory.","Method 2 is adaptive: when the space grows from $P_t$ to $P_{t+1}$ along a nested sequence, every previously drawn sample is kept, and only the additional samples for the new basis functions are drawn.","The construction works for any finite-dimensional subspace $P$ with a nonorthogonal basis, not just polynomials; the only practical requirements are evaluation of the basis on the grid and sampling from the error measure $\\rho$.","For domains with the $\\lambda$-rectangle property, $K=\\mathcal{O}(N^2\\log N)$ grid points suffice for the whole-domain error bound, so the method keeps the dimension-independent flavor of earlier irregular-domain frame methods."],"supporting_citations":[{"why":"Supplies the irregular-domain frame approximation setup, the random-grid construction, and the Nikolskii/lambda-rectangle estimates used to control the grid size K and the constant D.","marker":"[4]"},{"why":"Establishes the Christoffel-weighted sampling measure and the log-linear sample complexity M = O(N log N) that Method 1 adapts to discrete grids.","marker":"[11]"},{"why":"Provides the adaptive sampling construction, drawing fixed numbers of samples per orthonormal basis function, that Method 2 recycles when the space grows.","marker":"[19]"},{"why":"Supplies the Matrix Chernoff inequality used in Theorem 4.1 to convert the sample count M into bounds on C and the condition number of A.","marker":"[26]"},{"why":"Identifies the sum of squared orthonormal basis functions as the reciprocal Christoffel function, which justifies the choice of sampling weights.","marker":"[24]"},{"why":"Supplies the stability-and-accuracy analysis of least-squares projections that underlies the error decomposition in Theorem 3.1.","marker":"[10]"}],"fun_headline_variants":["Sampling trick tames least squares on any domain","Near-optimal sampling for general-domain least squares","O(N log N) samples fix least squares on irregular shapes","Christoffel-weighted sampling stabilizes least squares"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole-domain error guarantee depends on the fine grid being dense enough to keep the constant $D$ close to $1$; the paper proves a sufficient grid size only for domains with the $\\lambda$-rectangle property, while for arbitrary domains, including balls and simplices, this remains unproven.","fun_headline_variants_meta":{"raw":{"variants":["Sampling trick tames least squares on any domain","Near-optimal sampling for general-domain least squares","O(N log N) samples fix least squares on irregular shapes","Christoffel-weighted sampling stabilizes least squares"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000799,"raw_usage":{"total_tokens":3549,"prompt_tokens":1014,"completion_tokens":2535,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":2472}},"tokens_in":630,"tokens_out":2535,"duration_ms":18448,"temperature":1.0,"reasoning_tokens":2472,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:19:19.435804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a domain without the $\\lambda$-rectangle property, such as the unit ball or a simplex, take uniform $\\rho$ and a standard total-degree or hyperbolic-cross polynomial space, and set $K$ to the bound in Theorem 2.1 with fixed $\\gamma,\\delta$. Estimate $D=\\sup_{p\\in P}\\|p\\|_{L^2(\\Omega,\\rho)}/\\|p\\|_{L^2(\\Omega,\\tau)}$ over many independent $K$-grids: if for moderately large $N$ the ratio repeatedly exceeds $1/\\sqrt{1-\\delta}$ while the computable constant $C$ stays near $1$, then the whole-domain form of the theorem fails for such domains even though the grid-level guarantee holds.","supporting_citations":[{"cited_title":"Cohen and G","cited_arxiv_id":null,"evidence_quote":"Establishes the Christoffel-weighted sampling measure and the log-linear sample complexity M = O(N log N) that Method 1 adapts to discrete grids."},{"cited_title":"Adaptive approximation by optimal weighted least squares methods","cited_arxiv_id":"1807.00402","evidence_quote":"Provides the adaptive sampling construction, drawing fixed numbers of samples per orthonormal basis function, that Method 2 recycles when the space grows."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Matrix Chernoff inequality used in Theorem 4.1 to convert the sample count M into bounds on C and the condition number of A."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Identifies the sum of squared orthonormal basis functions as the reciprocal Christoffel function, which justifies the choice of sampling weights."},{"cited_title":"Cohen, M","cited_arxiv_id":null,"evidence_quote":"Supplies the stability-and-accuracy analysis of least-squares projections that underlies the error decomposition in Theorem 3.1."}],"review_version":1}