Pith. sign in

REVIEW 4 major objections 5 minor 66 references

Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that per-observation noise magnitudes and clean pairwise Euclidean distances can be recovered from corrupted distance matrices alone, with polynomial error bounds, no hyperparameters, and no low-rank or sparsity…

desk verdict A genuinely new hyperparameter-free distance-correction method with a clean LSAP invariance, but the central concentration lemma is imported and unverified, and the real-data demo sits outside the theorem's regime. read the letter →

arxiv 2507.18520 v2 pith:7V3ZVOXH submitted 2025-07-24 stat.ML cs.LGmath.STstat.TH

Keyi Li , Yuval Kluger , Boris Landa This is my paper · ORCID
classification stat.MLcs.LGmath.STstat.TH MSC 62H3062G20
keywords Euclideandistanceheteroskedasticnoisemagnitudeestimationcorrectionlinearsumassignmentproblemsub-Gaussianconcentrationhigh-dimensionalstatisticssingle-cellRNAsequencing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Under the additive corruption model $y_i = x_i + \eta_i$ with delocalized sub-Gaussian noise, this paper claims that each observation's noise magnitude $r_i = \|\eta_i\|_2^2$ and the clean pairwise squared Euclidean distances $D_{ij} = \|x_i - x_j\|_2^2$ can be recovered from the corrupted distance matrix alone. The mechanism is the approximate additive relation $\widetilde{D}_{ij} \approx D_{ij} + r_i + r_j$, which turns distance correction into estimating one number per point and subtracting. A linear-sum-assignment procedure finds two true near neighbors for every point even though the distances are corrupted, a three-equation system isolates each $r_i$, and the corrected matrix is $\widehat{D} = \widetilde{D} - \hat{r}\mathbf{1}^T - \mathbf{1}\hat{r}^T$. Theorem 3.6 bounds both normalized $\ell^1$ errors by $Ct(E(m) + n^{-\alpha})$ with probability at least $1 - n^{-t}$, converging to zero at polynomial rates as the feature dimension $m$ and sample size $n$ grow; the method has no hyperparameters and assumes no low-rank or sparsity structure on the clean data. If the claim holds, delocalized heteroskedastic noise can be neutralized as a preprocessing step for any distance-based downstream analysis.

What carries the argument

The load-bearing object is the approximate additive decomposition $\widetilde{D}_{ij} \approx D_{ij} + r_i + r_j$ of a corrupted squared distance into the clean distance plus two per-observation noise magnitudes, with the cross terms $\epsilon_{ij}$ provably negligible under the sub-Gaussian delocalization bound of Assumption 2 (Lemma F.1, which uses concentration estimates for the inner products $\langle x_i, \eta_j\rangle$ and $\langle \eta_i, \eta_j\rangle$). Two identities carry the argument: the assignment-invariance identity $\mathrm{Tr}(P^T\widetilde{D}) = \mathrm{Tr}(P^TD) + 2\sum_i r_i$, which holds for every permutation $P$ and guarantees that two rounds of the linear sum assignment problem on corrupted distances recover the same near neighbors as the clean problem; and the three-equation linear system (Eq. 12) among a point and its two assigned neighbors, whose solution isolates $r_i$. A graph-theoretic lemma (Lemma 3.5, proved with the marriage theorem through perfect matchings in each partition block of size at least four) bounds the assignment costs by the weighted average squared diameter of Assumption 3, which delivers the $n^{-\alpha}$ term of the error rate, while the concentration of the cross terms delivers the $E(m)$ term.

What would settle it

Generate a dataset whose noise is concentrated on a fixed small subset of coordinates — for instance $\eta_i$ with variance confined to the first $k \ll m$ coordinates while $\mathbb{E}\|\eta_i\|_2^2$ is held fixed — so that Assumption 2 is violated, and run Algorithm 1 while letting $m$ grow: the theory predicts that the normalized $\ell^1$ error $\frac{1}{n}\|\hat{r} - r\|_1$ will not decay, and an experiment either confirming that breakdown or showing the error still decays would settle whether the stated regime is exactly the boundary of the claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that in a high-dimensional regime where heteroskedastic noise does not concentrate in any particular direction, the per-observation noise magnitudes $r_i$ and the clean squared-distance matrix $D$ are identifiable from the corrupted squared distances $\widetilde{D}_{ij} = \|y_i - y_j\|_2^2$ alone. The corrupted distances inherit the additive structure $\widetilde{D}_{ij} \approx D_{ij} + r_i + r_j$, with cross terms $\epsilon_{ij} = 2\langle x_i - x_j, \eta_i - \eta_j\rangle - 2\langle \eta_i, \eta_j\rangle$ that concentrate near zero under the delocalization bound of Assumption 2. Because the linear-sum-assignment objective satisfies $\mathrm{Tr}(P^T\widetilde{D}) = \mathrm{Tr}(P^TD) + 2\sum_i r_i$ for every bijective assignment $P$, the extra term is constant and the optimal assignment on corrupted distances coincides with the optimal assignment on clean distances; two rounds of the assignment problem, with the second round masking the first, therefore identify two distinct true near neighbors for each point. The three corrupted distances among $\{i, \sigma_1(i), \sigma_2(i)\}$ then solve a $3 \times 3$ linear system whose unique solution is $\hat{r}_i = \tfrac{1}{2}(\widetilde{D}_{i\sigma_1(i)} + \widetilde{D}_{i\sigma_2(i)} - \widetilde{D}_{\sigma_1(i)\sigma_2(i)})$, and the corrected matrix follows by subtracting the estimated noise magnitudes. Theorem 3.6 states that, under Assumptions 1-3, the normalized $\ell^1$ errors of $\hat{r}$ and $\widehat{D}$ are bounded by $C't(E(m) + n^{-\alpha})$ and $C''t(E(m) + n^{-\alpha})$ with probability at least $1 - n^{-t}$, where $E(m) \to 0$ controls the cross-term concentration and $n^{-\alpha}$ controls how fast the assigned near-neighbor distances vanish as the sample grows.

Load-bearing premise

The argument collapses if the delocalization condition fails: the bound $E \le C/(m^{1/4}\sqrt{\log m})$ on the sub-Gaussian norm of the noise is what makes the cross terms $\epsilon_{ij}$ negligible, and without it the corrupted squared distance is not approximately $D_{ij} + r_i + r_j$, so neither the assignment-invariance identity nor the three-equation noise estimate has any justification.

Editorial extensions

If this is right

  • Given only the corrupted squared-distance matrix, per-observation noise magnitudes and clean pairwise distances can be estimated with normalized $\ell^1$ error $O(E(m) + n^{-\alpha})$ with probability at least $1 - n^{-t}$, a rate that is polynomial in both the feature dimension and the sample size (Theorem 3.6).
  • The procedure is hyperparameter-free and needs no knowledge of the noise distribution beyond sub-Gaussianity and delocalization, and no low-rank, sparsity, or label information about the clean data.
  • Distance-based downstream computations inherit the correction: Gaussian kernel similarities, KNN graphs, and self-tuning kernel Laplacians built from $\widehat{D}$ track their clean-data counterparts, with nearest-neighbor identification accuracy improving roughly two- to three-fold in the paper's simulations.
  • The geometric condition on the clean data (partitionability with small weighted squared diameter) holds with explicit polynomial rates for iid samples from essentially any distribution on a bounded hypercube, and for mixtures of embedded low-dimensional geometries (Theorem 3.3 and Corollary 3.4).
  • On a PBMC single-cell RNA sequencing dataset, the estimated noise magnitudes track the inverse-library-size prediction of a standard Poisson noise model, and KNN graphs built from corrected distances show markedly lower cross-cell-type neighborhood impurity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit that the same correction could be inserted into any distance-based pipeline — spectral clustering, diffusion maps, multidimensional scaling, or $k$-means — since it outputs a full corrected distance matrix rather than a graph.
  • A testable extension the paper itself sketches is a global least-squares fit over all $n$ triangle systems, in which each $r_i$ appears three times; this could replace the per-point two-neighbor scheme and possibly trade the $O(n^3)$ assignment solver for better finite-sample stability.
  • The practical boundary of the claim is the delocalization condition: for sparse count-type data such as raw gene expression matrices, noise can concentrate in particular coordinates, and the paper's own scRNA-seq experiment only reaches the Poisson calibration after library-size normalization, suggesting that preprocessing is required before the assumption holds.
  • If the delocalization bound were relaxed to weaker tail classes such as sub-exponential noise — a direction the discussion names — the same three-equation estimator would likely survive, since only the concentration of the cross terms $\epsilon_{ij}$ is actually used.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies the additive noise model y_i = x_i + η_i in R^m with independent, heteroskedastic sub-Gaussian noise, and claims that from the corrupted squared distances alone one can recover per-observation squared noise magnitudes r_i = ||η_i||^2 and clean squared distances ||x_i - x_j||^2. Algorithm 1 solves two linear-sum-assignment problems on the corrupted distance matrix, uses the two assigned near neighbors per point to form a 3x3 linear system whose solution gives the noise estimate, and subtracts the corresponding rank-one correction. Section 3 states Assumptions 1-3 and Theorem 3.6, which bounds normalized L1 errors by C t(E(m) + n^{-α}) with high probability. Section 4 provides synthetic validation, kernel and KNN improvements, self-tuning kernel experiments, and a PBMC scRNA-seq application. The main proof elements are the additive invariance of the LSAP in Eq. (14), the Hall's theorem construction in Lemma 3.5, and a concentration lemma (F.1) imported from the authors' prior work [27].

Significance. If the theorem's rates hold, the paper gives a striking hyperparameter-free consistency result: per-observation noise magnitudes and clean pairwise distances can be recovered from corrupted distances alone, without low-rank or sparsity assumptions on the clean data. The clean invariance in Eq. (14), the two-round assignment design, and the Hall-theorem argument in Lemma 3.5 are genuine contributions, and the synthetic experiments in Section 4.1 match the predicted m^{-1/2} and n^{-2/3} scalings. However, the result is conditional on a concentration lemma that is not proved under the stated assumptions, and the probabilistic union-bound step needs a stronger scaling assumption than the one stated; these need to be fixed before the headline claim is fully supported.

major comments (4)
  1. [Appendix F, Lemma F.1] Lemma F.1 (Eq. 73) is the load-bearing concentration result: it is used to justify Eq. (9) and, through Appendix G, both bounds (22) and (23). Its proof, however, is not self-contained: it cites equations (SM1.5) and (SM1.11) of the supplementary material of [27], a paper with overlapping authorship, and it is not documented that those equations hold under the present Assumption 2 scaling E ≤ C/(m^{1/4} sqrt(log m)). If the imported bounds require a stronger decay such as E ≤ C m^{-1/2}, the displayed E(m) rate in Theorem 3.6 would not follow. Please either give a full proof of Lemma F.1 under Assumption 2 or state the exact lemma from [27] with its hypotheses and verify them.
  2. [Appendix G / Assumption 1] The probability statement of Theorem 3.6 does not follow from the union-bound argument as written. Lemma F.1 gives a failure probability of m^{-t} per pair; after union-bounding over n pairs in Eq. (91) or n^2 pairs in Eq. (92), and using m ≥ n^γ, the failure probability is at least n^{2-γt} (respectively n^{1-γt}), which can be bounded by n^{-t} only when γ > 1 and t ≥ 2/(γ-1). Assumption 1 only requires γ > 0, so for 0 < γ ≤ 1 the claimed 1 - n^{-t} guarantee has not been established. The assumption or the probability statement needs to be adjusted accordingly.
  3. [Abstract and Section 1.2] The abstract and Section 1.2 state that the normalized L1 errors converge to zero 'at a polynomial rate' as both m and n increase. Under the largest noise level allowed by Assumption 2, however, E(m) = sqrt(log m) · max(E, E^2 sqrt(m)) is only O((log m)^{-1/2}), which is slower than any polynomial in m; the same is true for the Gaussian example discussed after Assumption 2. Thus the polynomial-rate claim is not supported by Theorem 3.6 unless the noise scale is further restricted or the statement is weakened to convergence in m and polynomial convergence in n.
  4. [Section 4.4, Eqs. (32)-(33)] The scRNA-seq demonstration may lie outside the theorem's regime. After library-size normalization (32), the Poisson model gives η_i ≈ ỹ_i - E[ỹ_i] with sub-Gaussian norm on the order of sqrt(max_j λ_ij)/L_i; for low-depth cells this can exceed the Assumption 2 threshold C/(m^{1/4} sqrt(log m)) at m ≈ 3.3 × 10^4. The paper should either verify Assumption 2 for the downsampled data or present this experiment as an empirical illustration outside the stated guarantees, rather than as confirmation of Theorem 3.6.
minor comments (5)
  1. [Theorem 3.3] Theorem 3.3 is stated for samples from [0,1]^d, but Assumption 3 requires ||x_i||_2 ≤ 1; for d > 1 points in [0,1]^d need not satisfy this. Please scale the cube to [0, 1/√d]^d (as done in Corollary 3.4) or state the normalization explicitly, adjusting the diameter bounds accordingly.
  2. [Figure 3(b)] In Section 4.1, the claim that n^{-2/3} is much larger than E(m) is not strictly true over the full displayed range: with m = 5 × 10^5, E(m) ≈ 5 × 10^{-3} while n^{-2/3} falls below this near n = 10^4. The observed n-scaling may be partially affected by the E(m) term; please state the crossover or use a larger m.
  3. [Eq. (26)] The SNR estimator in Eq. (26) can become negative when r̂_i > ||y_i||_2^2; the paper does not discuss how such cases are treated in the experiments.
  4. [Appendix E] The notation eO_n and eO_{m,n} is introduced only in Definition E.1; in Eqs. (81) and (88) the term eO_n(n^{-α+1}) should be eO_{m,n}(...) for consistency with the definition.
  5. [References] The reference to Zelnik-Manor and Perona appears as 'Zelnik-manor' in [65]; please fix the capitalization.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the derivation is self-contained algebra, with a published prior-work concentration lemma as an external (non-circular) dependency.

full rationale

The derivation chain is not circular. Eq. (2) defines r_i as the squared noise norm and eps_ij as the cross terms; Eq. (14) shows that any permutation's LSAP objective changes by the same additive constant 2*sum_i r_i, an exact algebraic identity that does not presuppose the target estimates. Eq. (7) solves a 3x3 linear system for r_i from three corrupted distances, and Theorem 3.6's proof in Appendix G bounds the resulting errors using Lemma 3.5 (derived from Assumption 3) and Lemma F.1. Lemma F.1 is not proved inside this manuscript; it cites concentration bounds (SM1.5) and (SM1.11) from [27], a published SIAM paper with overlapping authorship. This is a notable external dependency: a careful reviewer should confirm that the cited lemmas hold under the present Assumption 2 scaling. However, citing a published, parameter-free concentration inequality is not circular: the cited result does not include this paper's target conclusion, and the LSAP-invariance and linear-system algebra are independently developed here. The numerical alpha=2/3 in Section 4.1 is read off from observed LSAP costs and used to illustrate the n^{-alpha} rate; because Theorem 3.6 supplies an upper bound rather than a forced equality, this is an empirical consistency check, not a fitted parameter renamed as a prediction. No self-definitional, fitted-input, renaming, or uniqueness-importing circularity is present, so the score is only 1, reflecting the self-citation dependency without treating it as a circular step.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The method introduces no new entities or fitted constants. Its assumptions are a zero-mean independent additive noise model, polynomial scaling m >= n^gamma, a delocalized sub-Gaussian noise class, and a density or geometry condition that is proved to hold for bounded i.i.d. data. The most consequential external dependency is the concentration result cited from [27].

assumptions (7)
  • domain assumption Additive noise model y_i = x_i + eta_i with independent zero-mean noise vectors (Eq. 1).
    All theory and the correction formula are tied to this model; if the corruption is not additive, the interpretation of r_i as squared noise norm breaks.
  • domain assumption Assumption 1: m >= n^gamma for some gamma > 0.
    The proof needs n and m to grow together to make union bounds over O(n^2) epsilon terms work.
  • domain assumption Assumption 2: sub-Gaussian noise with E <= C/(m^{1/4} sqrt(log m)).
    This delocalization condition is what forces epsilon_ij in Eq. (2) to concentrate around zero; it is the main modeling assumption about the noise distribution.
  • domain assumption Assumption 3: the clean dataset has a partition of subsets of size at least 4 with weighted average squared diameter <= c n^{-alpha}.
    This guarantees the near-neighbor squared distances used in Eq. (7) decay with n; Theorem 3.3 proves it holds for i.i.d. samples from bounded hypercubes.
  • standard math Hall's marriage theorem and Lemma C.2 sufficient condition for perfect matchings.
    Used in Lemma 3.5 to construct a feasible second-round assignment avoiding the masked cost entries.
  • domain assumption Concentration inequalities (SM1.5) and (SM1.11) from [27] for sub-Gaussian inner products.
    Lemma F.1 in the appendix relies on these cited bounds; they are not derived in the present paper and are a dependency of the main theorem.
  • standard math Hoeffding's inequality in the proof of Theorem 3.3.
    Used to establish that bins contain enough points with high probability.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise." pith.science (2026). https://pith.science/paper/7V3ZVOXH

@misc{pith2026250718520,
  author       = {Pith},
  title        = {Pith review of: Euclidean Distance Deflation Under High-Dimensional Heteroskedastic Noise},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7V3ZVOXH}},
  note         = {Machine review of arXiv:2507.18520}
}
abstract

Pairwise Euclidean distance calculation is a fundamental step in many machine learning and data analysis algorithms. In real-world applications, however, these distances are frequently distorted by heteroskedastic noise$\unicode{x2014}$a prevalent form of inhomogeneous corruption characterized by variable noise magnitudes across data observations. Such noise inflates the computed distances in a nontrivial way, leading to misrepresentations of the underlying data geometry. In this work, we address the tasks of estimating the noise magnitudes per observation and correcting the pairwise Euclidean distances under heteroskedastic noise. Perhaps surprisingly, we show that in general high-dimensional settings and without assuming prior knowledge on the clean data structure or noise distribution, both tasks can be performed reliably, even when the noise levels vary considerably. Specifically, we develop a principled, hyperparameter-free approach that jointly estimates the noise magnitudes and corrects the distances. We provide theoretical guarantees for our approach, establishing probabilistic bounds on the estimation errors of both noise magnitudes and distances. These bounds, measured in the normalized $\ell_1$ norm, converge to zero at polynomial rates as both feature dimension and dataset size increase. Experiments on synthetic datasets demonstrate that our method accurately estimates distances in challenging regimes, significantly improving the robustness of subsequent distance-based computations. Notably, when applied to single-cell RNA sequencing data, our method yields noise magnitude estimates consistent with an established prototypical model, enabling accurate nearest neighbor identification that is fundamental to many downstream analyses.

Figures

Figures reproduced from arXiv: 2507.18520 by the authors.

Figure 1
Figure 1. Key phenomena underlying our approach in the regime of large sample size ( [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the simulated data in Section 4.1 and the empirical LSAP costs (a) Simulated data [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Empirical evaluation of estimation errors of Algorithm 1. (a) Normalized [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Results of applying our approach to simulated data from a circle corrupted by varying noise. [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Self-tuning kernels with the corrected distances reveal the clean geometry of a heteroskedastic [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Application to a downsampled scRNA-seq dataset of PBMC. (a) Comparison of estimated noise [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 56 canonical work pages

  1. [27]

    Robust inference of manifold density and geometry by doubly stochas- tic scaling.SIAM Journal on Mathematics of Data Science, 5(3):589–614, 2023

    Boris Landa and Xiuyuan Cheng. Robust inference of manifold density and geometry by doubly stochas- tic scaling.SIAM Journal on Mathematics of Data Science, 5(3):589–614, 2023

    work page 2023

  2. [1]

    Comparison of transformations for single-cell rna-seq data.Nature Methods, 20(5):665–672, May 2023

    Constantin Ahlmann-Eltze and Wolfgang Huber. Comparison of transformations for single-cell rna-seq data.Nature Methods, 20(5):665–672, May 2023

    work page 2023

  3. [2]

    Laplacian eigenmaps for dimensionality reduction and data repre- sentation.Neural Computation, 15(6):1373–1396, 2003

    Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data repre- sentation.Neural Computation, 15(6):1373–1396, 2003

    work page 2003

  4. [3]

    The metric nearness problem.SIAM Journal on Matrix Analysis and Applications, 30(1):375–396, 2008

    Justin Brickell, Inderjit S Dhillon, Suvrit Sra, and Joel A Tropp. The metric nearness problem.SIAM Journal on Matrix Analysis and Applications, 30(1):375–396, 2008

    work page 2008

  5. [4]

    Buades, B

    A. Buades, B. Coll, and J.-M. Morel. A non-local algorithm for image denoising. In2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 2, pages 60–65 vol. 2, 2005

    2005

  6. [5]

    Society for Industrial and Applied Mathematics, 2012

    Rainer Burkard, Mauro Dell’Amico, and Silvano Martello.Assignment Problems. Society for Industrial and Applied Mathematics, 2012

    work page 2012

  7. [6]

    The single-cell transcriptional landscape of mammalian organogenesis.Nature, 566(7745):496–502, February 2019

    Junyue Cao, Malte Spielmann, Xiaojie Qiu, Xingfan Huang, Daniel M Ibrahim, Andrew J Hill, Fan Zhang, Stefan Mundlos, Lena Christiansen, Frank J Steemers, Cole Trapnell, and Jay Shendure. The single-cell transcriptional landscape of mammalian organogenesis.Nature, 566(7745):496–502, February 2019

    2019

  8. [7]

    Xiuyuan Cheng and Boris Landa. Bi-stochastically normalized graph laplacian: convergence to man- ifold laplacian and robustness to outlier noise.Information and Inference: A Journal of the IMA, 13(4):iaae026, 2024. 30

    work page 2024

Show all 66 references
  1. [8]

    Big data for remote sensing: Challenges and opportunities.Proceedings of the IEEE, 104(11):2207–2219, 2016

    Mingmin Chi, Antonio Plaza, J´ on Atli Benediktsson, Zhongyi Sun, Jinsheng Shen, and Yangyong Zhu. Big data for remote sensing: Challenges and opportunities.Proceedings of the IEEE, 104(11):2207–2219, 2016

    2016

  2. [9]

    Coifman and St´ ephane Lafon

    Ronald R. Coifman and St´ ephane Lafon. Diffusion maps.Applied and Computational Harmonic Anal- ysis, 21(1):5–30, 2006. Special Issue: Diffusion Maps and Wavelets

    2006

  3. [10]

    Coifman and Mauro Maggioni

    Ronald R. Coifman and Mauro Maggioni. Diffusion wavelets.Applied and Computational Harmonic Analysis, 21(1):53–94, 2006. Special Issue: Diffusion Maps and Wavelets

    2006

  4. [11]

    Convolutional neural networks on graphs with fast localized spectral filtering

    Micha¨ el Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 29. C...

    2016

  5. [12]

    Farrell, Yiqun Wang, Samantha J

    Jeffrey A. Farrell, Yiqun Wang, Samantha J. Riesenfeld, Karthik Shekhar, Aviv Regev, and Alexander F. Schier. Single-cell reconstruction of developmental trajectories during zebrafish embryogenesis.Science, 360(6392):eaar3131, 2018

    2018

  6. [13]

    Community detection in graphs.Physics Reports, 486(3):75–174, 2010

    Santo Fortunato. Community detection in graphs.Physics Reports, 486(3):75–174, 2010

    2010

  7. [14]

    Review of wavelet denoising algorithms.Multimedia Tools and Applications, 82(27):41539– 41569, 2023

    Aminou Halidou, Youssoufa Mohamadou, Ado Adamou Abba Ari, and Edinio Jocelyn Gbadoubissa Zacko. Review of wavelet denoising algorithms.Multimedia Tools and Applications, 82(27):41539– 41569, 2023

    2023

  8. [15]

    Kenneth M. Hall. An r-dimensional quadratic placement algorithm.Management Science, 17(3):219– 229, 1970

    1970

  9. [16]

    P. Hall. On representatives of subsets.Journal of the London Mathematical Society, s1-10(1):26–30, 1935

    1935

  10. [17]

    Hammond, Pierre Vandergheynst, and R´ emi Gribonval

    David K. Hammond, Pierre Vandergheynst, and R´ emi Gribonval. Wavelets on graphs via spectral graph theory.Applied and Computational Harmonic Analysis, 30(2):129–150, 2011

    2011

  11. [18]

    Missing data and technical variability in single-cell rna-sequencing experiments.Biostatistics, 19(4):562–578, 11 2017

    Stephanie C Hicks, F William Townes, Mingxiang Teng, and Rafael A Irizarry. Missing data and technical variability in single-cell rna-sequencing experiments.Biostatistics, 19(4):562–578, 11 2017

    2017

  12. [19]

    Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963

    Wassily Hoeffding. Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58(301):13–30, 1963

    1963

  13. [20]

    Loopy belief propagation for bipartite maximum weight b-matching

    Bert Huang and Tony Jebara. Loopy belief propagation for bipartite maximum weight b-matching. In Marina Meila and Xiaotong Shen, editors,Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 ofProceedings of Machine Learning R...

    2007

  14. [21]

    Graph construction and b-matching for semi-supervised learning

    Tony Jebara, Jun Wang, and Shih-Fu Chang. Graph construction and b-matching for semi-supervised learning. InProceedings of the 26th annual international conference on machine learning, pages 441–448, 2009

    2009

  15. [22]

    Principal component analysis: a review and recent developments

    Ian T Jolliffe and Jorge Cadima. Principal component analysis: a review and recent developments. Philosophical transactions of the royal society A: Mathematical, Physical and Engineering Sciences, 374(2065):20150202, 2016

    2016

  16. [23]

    On information plus noise kernel random matrices.The Annals of Statistics, 38(5):3191 – 3216, 2010

    Noureddine El Karoui. On information plus noise kernel random matrices.The Annals of Statistics, 38(5):3191 – 3216, 2010

    2010

  17. [24]

    Graph connection Laplacian methods can be made robust to noise.The Annals of Statistics, 44(1):346 – 372, 2016

    Noureddine El Karoui and Hau-Tieng Wu. Graph connection Laplacian methods can be made robust to noise.The Annals of Statistics, 44(1):346 – 372, 2016

    2016

  18. [25]

    Spectral biclustering of microarray data: coclustering genes and conditions.Genome research, 13(4):703–716, 2003

    Yuval Kluger, Ronen Basri, Joseph T Chang, and Mark Gerstein. Spectral biclustering of microarray data: coclustering genes and conditions.Genome research, 13(4):703–716, 2003. 31

    2003

  19. [26]

    H. W. Kuhn. The hungarian method for the assignment problem.Naval Research Logistics Quarterly, 2(1-2):83–97, 1955

    1955

  20. [28]

    Doubly stochastic normalization of the gaussian kernel is robust to heteroskedastic noise.SIAM journal on mathematics of data science, 3(1):388–413, 2021

    Boris Landa, Ronald R Coifman, and Yuval Kluger. Doubly stochastic normalization of the gaussian kernel is robust to heteroskedastic noise.SIAM journal on mathematics of data science, 3(1):388–413, 2021

    2021

  21. [29]

    The steerable graph laplacian and its application to filtering image datasets.SIAM Journal on Imaging Sciences, 11(4):2254–2304, 2018

    Boris Landa and Yoel Shkolnisky. The steerable graph laplacian and its application to filtering image datasets.SIAM Journal on Imaging Sciences, 11(4):2254–2304, 2018

    2018

  22. [30]

    Introduction to inequalities.Marjorie Lohwater, 1982

    Arthur Lohwater. Introduction to inequalities.Marjorie Lohwater, 1982

    1982

  23. [31]

    Lovasz.Matching Theory (North-Holland mathematics studies)

    L. Lovasz.Matching Theory (North-Holland mathematics studies). Elsevier Science Ltd., GBR, 1986

    1986

  24. [32]

    Current best practices in single-cell rna-seq analysis: a tutorial

    Malte D Luecken and Fabian J Theis. Current best practices in single-cell rna-seq analysis: a tutorial. Molecular Systems Biology, 15(6):e8746, 2019

    2019

  25. [33]

    Highly parallel genome-wide expression profiling of individual cells using nanoliter droplets.Cell, 161(5):1202–1214, 2015

    Evan Z Macosko, Anindita Basu, Rahul Satija, James Nemesh, Karthik Shekhar, Melissa Goldman, Itay Tirosh, Allison R Bialas, Nolan Kamitaki, Emily M Martersteck, et al. Highly parallel genome-wide expression profiling of individual cells using nanoliter droplets.Cell, 161(5):12...

    2015

  26. [34]

    Some methods for classification and analysis of multivariate observations

    James MacQueen. Some methods for classification and analysis of multivariate observations. InProceed- ings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, volume 5, pages 281–298. University of California press, 1967

    1967

  27. [35]

    Manifold learning with bi-stochastic kernels.IMA Journal of Applied Mathematics, 84(3):455–482, 2019

    Nicholas F Marshall and Ronald R Coifman. Manifold learning with bi-stochastic kernels.IMA Journal of Applied Mathematics, 84(3):455–482, 2019

    2019

  28. [36]

    Umap: Uniform manifold approximation and projec- tion for dimension reduction, 2020

    Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projec- tion for dimension reduction, 2020

    2020

  29. [37]

    Meyer and Xilin Shen

    Fran¸ cois G. Meyer and Xilin Shen. Perturbation of the eigenvectors of the graph laplacian: Application to image denoising.Applied and Computational Harmonic Analysis, 36(2):326–334, 2014

    2014

  30. [38]

    A revised airway epithelial hierarchy includes CFTR-expressing ionocytes.Nature, 560(7718):319–324, August 2018

    Daniel T Montoro, Adam L Haber, Moshe Biton, Vladimir Vinarsky, Brian Lin, Susan E Birket, Feng Yuan, Sijia Chen, Hui Min Leung, Jorge Villoria, Noga Rogel, Grace Burgin, Alexander M Tsankov, Avinash Waghray, Michal Slyper, Julia Waldman, Lan Nguyen, Danielle Dionne, Orit Roze...

    2018

  31. [39]

    Algorithms for the assignment and transportation problems.Journal of the society for industrial and applied mathematics, 5(1):32–38, 1957

    James Munkres. Algorithms for the assignment and transportation problems.Journal of the society for industrial and applied mathematics, 5(1):32–38, 1957

    1957

  32. [40]

    On spectral clustering: Analysis and an algorithm

    Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In T. Dietterich, S. Becker, and Z. Ghahramani, editors,Advances in Neural Information Processing Systems, volume 14. MIT Press, 2001

    2001

  33. [41]

    Graph laplacian regularization for image denoising: Analysis in the continuous domain.IEEE Transactions on Image Processing, 26(4):1770–1785, 2017

    Jiahao Pang and Gene Cheung. Graph laplacian regularization for image denoising: Analysis in the continuous domain.IEEE Transactions on Image Processing, 26(4):1770–1785, 2017

    2017

  34. [42]

    The human cell atlas.elife, 6:e27041, 2017

    Aviv Regev, Sarah A Teichmann, Eric S Lander, Ido Amit, Christophe Benoist, Ewan Birney, Bernd Bodenmiller, Peter Campbell, Piero Carninci, Menna Clatworthy, et al. The human cell atlas.elife, 6:e27041, 2017. 32

    2017

  35. [43]

    Poisson noise reduc- tion with non-local pca.J

    Joseph Salmon, Zachary Harmany, Charles-Alban Deledalle, and Rebecca Willett. Poisson noise reduc- tion with non-local pca.J. Math. Imaging Vis., 48(2):279–294, February 2014

    2014

  36. [44]

    Separating measurement and expression models clarifies con- fusion in single-cell RNA sequencing analysis.Nature Genetics, 53(6):770–777, June 2021

    Abhishek Sarkar and Matthew Stephens. Separating measurement and expression models clarifies con- fusion in single-cell RNA sequencing analysis.Nature Genetics, 53(6):770–777, June 2021

    2021

  37. [45]

    Purnamrita Sarkar and Peter J. Bickel. Role of normalization in spectral clustering for stochastic blockmodels.The Annals of Statistics, 43(3), June 2015

    2015

  38. [46]

    Spectralnet: Spectral clustering using deep neural networks, 2018

    Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks, 2018

    2018

  39. [47]

    Analysis of call centre arrival data using singular value decompo- sition.Applied Stochastic Models in Business and Industry, 21(3):251–263, 2005

    Haipeng Shen and Jianhua Z Huang. Analysis of call centre arrival data using singular value decompo- sition.Applied Stochastic Models in Business and Industry, 21(3):251–263, 2005

    2005

  40. [48]

    Missing information reconstruction of remote sensing data: A technical review.IEEE Geoscience and Remote Sensing Magazine, 3(3):61–85, 2015

    Huanfeng Shen, Xinghua Li, Qing Cheng, Chao Zeng, Gang Yang, Huifang Li, and Liangpei Zhang. Missing information reconstruction of remote sensing data: A technical review.IEEE Geoscience and Remote Sensing Magazine, 3(3):61–85, 2015

    2015

  41. [49]

    Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst

    David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.IEEE Signal Processing Magazine, 30(3):83–98, 2013

    2013

  42. [50]

    Diffusion interpretation of nonlocal neighborhood filters for signal denoising.SIAM Journal on Imaging Sciences, 2(1):118–139, 2009

    Amit Singer, Yoel Shkolnisky, and Boaz Nadler. Diffusion interpretation of nonlocal neighborhood filters for signal denoising.SIAM Journal on Imaging Sciences, 2(1):118–139, 2009

    2009

  43. [51]

    Concerning nonnegative matrices and doubly stochastic matrices

    Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343–348, 1967

    1967

  44. [52]

    Triangle fixing algorithms for the metric nearness problem

    Suvrit Sra, Joel Tropp, and Inderjit Dhillon. Triangle fixing algorithms for the metric nearness problem. Advances in Neural Information Processing Systems, 17, 2004

    2004

  45. [53]

    Tamuz, T

    O. Tamuz, T. Mazeh, and S. Zucker. Correcting systematic effects in a large set of photometric light curves.Monthly Notices of the Royal Astronomical Society, 356(4):1466–1470, 02 2005

    2005

  46. [54]

    An efficient algorithm for theℓ p norm based metric nearness problem.Mathematics of Computation, 2024

    Peipei Tang, Bo Jiang, and Chengjing Wang. An efficient algorithm for theℓ p norm based metric nearness problem.Mathematics of Computation, 2024

    2024

  47. [55]

    Torgerson

    Warren S. Torgerson. Multidimensional scaling: I. theory and method.Psychometrika, 17(4):401–419, Dec 1952

    1952

  48. [56]

    Snekhorn: Dimension reduction with symmetric entropic affinities.Advances in Neural Information Processing Systems, 36:44470–44487, 2023

    Hugues Van Assel, Titouan Vayer, R´ emi Flamary, and Nicolas Courty. Snekhorn: Dimension reduction with symmetric entropic affinities.Advances in Neural Information Processing Systems, 36:44470–44487, 2023

    2023

  49. [57]

    Visualizing data using t-sne.Journal of Machine Learning Research, 9(86):2579–2605, 2008

    Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne.Journal of Machine Learning Research, 9(86):2579–2605, 2008

    2008

  50. [58]

    Cambridge university press, 2018

    Roman Vershynin.High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  51. [59]

    De Jager, Orit Rozenblatt-Rosen, Andrew A

    Alexandra-Chlo´ e Villani, Rahul Satija, Gary Reynolds, Siranush Sarkizova, Karthik Shekhar, James Fletcher, Morgane Griesbeck, Andrew Butler, Shiwei Zheng, Suzan Lazo, Laura Jardine, David Dixon, Emily Stephenson, Emil Nilsson, Ida Grundberg, David McDonald, Andrew Filby, Wei...

    2017

  52. [60]

    Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion.Journal of machine learning research, 11(12), 2010

    Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and L´ eon Bottou. Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion.Journal of machine learning research, 11(12), 2010. 33

    2010

  53. [61]

    A tutorial on spectral clustering, 2007

    Ulrike von Luxburg. A tutorial on spectral clustering, 2007

    2007

  54. [62]

    A noise and background reduction method for component detection in liquid chromatography/mass spectrometry.Analytical chemistry, 68(20):3602– 3606, 1996

    Willem Windig, J Martin Phalp, and Alan W Payne. A noise and background reduction method for component detection in liquid chromatography/mass spectrometry.Analytical chemistry, 68(20):3602– 3606, 1996

    1996

  55. [63]

    Spectral convergence of diffusion maps: Improved error bounds and an alternative normalization.SIAM Journal on Numerical Analysis, 59(3):1687–1734, 2021

    Caroline L Wormell and Sebastian Reich. Spectral convergence of diffusion maps: Improved error bounds and an alternative normalization.SIAM Journal on Numerical Analysis, 59(3):1687–1734, 2021

    2021

  56. [64]

    Intrinsic randomness as a measure of quantum coherence.Physical Review A, 92(2):022124, 2015

    Xiao Yuan, Hongyi Zhou, Zhu Cao, and Xiongfeng Ma. Intrinsic randomness as a measure of quantum coherence.Physical Review A, 92(2):022124, 2015

    2015

  57. [65]

    Self-tuning spectral clustering

    Lihi Zelnik-manor and Pietro Perona. Self-tuning spectral clustering. In L. Saul, Y. Weiss, and L. Bottou, editors,Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004

    2004

  58. [66]

    Grace X. Y. Zheng, Jessica M. Terry, Phillip Belgrader, Paul Ryvkin, Zachary W. Bent, Ryan Wilson, Solongo B. Ziraldo, Tobias D. Wheeler, Geoff P. McDermott, Junjie Zhu, Mark T. Gregory, Joe Shuga, Luz Montesclaros, Jason G. Underwood, Donald A. Masquelier, Stefanie Y. Nishimu...

    2017

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.