The Experts below are selected from a list of 79743 Experts worldwide ranked by ideXlab platform
Sebastien Roch - One of the best experts on this subject based on the ideXlab platform.
-
species trees from gene trees despite a high rate of lateral genetic transfer a tight bound
Symposium on Discrete Algorithms, 2016Co-Authors: Constantinos Daskalakis, Sebastien RochAbstract:Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of lateral genetic transfer (LGT), whereby a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from (but related to) the species phylogeny. In previous work, a stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a Constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a Constant Probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching bound in the negative direction (up to a Constant).
-
species trees from gene trees despite a high rate of lateral genetic transfer a tight bound extended abstract
Symposium on Discrete Algorithms, 2016Co-Authors: Constantinos Daskalakis, Sebastien RochAbstract:Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of lateral genetic transfer (LGT), whereby a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from (but related to) the species phylogeny. In previous work, a stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a Constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a Constant Probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching bound in the negative direction (up to a con-
P Andreani - One of the best experts on this subject based on the ideXlab platform.
-
the correct estimate of the Probability of false detection of the matched filter in weak signal detection problems iii peak distribution method versus the gumbel distribution method
Astronomy and Astrophysics, 2019Co-Authors: R Vio, P Andreani, A Biggs, N HayatsuAbstract:The matched filter (MF) represents one of the main tools to detect signals from known sources embedded in the noise. In the Gaussian case the noise is assumed to be the realization of a Gaussian random field (GRF). The most important property of the MF, the maximization of the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA), makes it one of the most popular techniques. However, the MF technique relies upon the a priori knowledge of the number and the position of the searched signals in the GRF which usually are not available. A typical way out is to assume that the position of a signal coincides with one of the peaks in the matched filtered data. A detection is claimed when the Probability that a given peak is due only to the noise (i.e. the PFA) is smaller than a prefixed threshold. In this case the Probability density function (PDF) of the amplitudes has to be used for the computation of the PFA, which is different from the Gaussian. Moreover, the Probability that a detection is false depends on the number of peaks present in the filtered GRF, the greater the number of peaks in a GRF, the higher the Probability of peaks due to the noise that exceed the detection threshold. If not taken into account, the PFA can be severely underestimated. Many solutions proposed to this problem are non-parametric hence not able to exploit all the available information. This limitation has been overcome by means of two efficient parametric approaches, one based on the PDF of the peak amplitudes of a smooth and isotropic GRF whereas the other uses the Gumbel distribution (the asymptotic PDF of the corresponding extreme). Simulations and ALMA maps show that, although the two methods produce almost identical results, the first is more flexible and allows us to check the reliability of the detection procedure.
-
correct estimate of the Probability of false detection of the matched filter in weak signal detection problems iii peak distribution method versus the gumbel distribution method
arXiv: Instrumentation and Methods for Astrophysics, 2019Co-Authors: R Vio, P Andreani, A Biggs, N HayatsuAbstract:The matched filter (MF) represents one of the main tools to detect signals from known sources embedded in the noise. In the Gaussian case the noise is assumed to be the realization of a Gaussian random field (GRF). The most important property of the MF, the maximization of the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA), makes it one of the most popular techniques. However, the MF technique relies upon the a priori knowledge of the number and the position of the searched signals in the GRF which usually are not available. A typical way out is to assume that the position of a signal coincides with one of the peaks in the matched filtered data. A detection is claimed when the Probability that a given peak is due only to the noise (i.e. the PFA) is smaller than a prefixed threshold. In this case the Probability density function (PDF) of the amplitudes has to be used for the computation of the PFA, which is different from the Gaussian. Moreover, the Probability that a detection is false depends on the number of peaks present in the filtered GRF, the greater the number of peaks in a GRF, the higher the Probability of peaks due to the noise that exceed the detection threshold. If not taken into account, the PFA can be severely underestimated. Many solutions proposed to this problem are non-parametric hence not able to exploit all the available information. This limitation has been overcome by means of two efficient parametric approaches, one based on the PDF of the peak amplitudes of a smooth and isotropic GRF whereas the other uses the Gumbel distribution (the asymptotic PDF of the corresponding extreme). Simulations and ALMA maps show that, although the two methods produce almost identical results, the first is more flexible and allows us to check the reliability of the detection procedure.
-
the correct estimate of the Probability of false detection of the matched filter in weak signal detection problems ii further results with application to a set of alma and atca data
Astronomy and Astrophysics, 2017Co-Authors: R Vio, C Verges, P AndreaniAbstract:The matched filter (MF) is one of the most popular and reliable techniques to the detect signals of known structure and amplitude smaller than the level of the contaminating noise. Under the assumption of stationary Gaussian noise, MF maximizes the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA). This property relies upon a priori knowledge of the position of the searched signals, which is usually not available. Recently, it has been shown that when applied in its standard form, MF may severely underestimate the PFA. As a consequence the statistical significance of features that belong to noise is overestimated and the resulting detections are actually spurious. For this reason, an alternative method of computing the PFA has been proposed that is based on the Probability density function (PDF) of the peaks of an isotropic Gaussian random field. In this paper we further develop this method. In particular, we discuss the statistical meaning of the PFA and show that, although useful as a preliminary step in a detection procedure, it is not able to quantify the actual reliability of a specific detection. For this reason, a new quantity is introduced called the specific Probability of false alarm (SPFA), which is able to carry out this computation. We show how this method works in targeted simulations and apply it to a few interferometric maps taken with the Atacama Large Millimeter/submillimeter Array (ALMA) and the Australia Telescope Compact Array (ATCA). We select a few potential new point sources and assign an accurate detection reliability to these sources.
-
the correct estimate of the Probability of false detection of the matched filter in the detection of weak signals ii further results with application to a set of alma and atca data
arXiv: Instrumentation and Methods for Astrophysics, 2017Co-Authors: R Vio, C Verges, P AndreaniAbstract:The matched filter (MF) is one of the most popular and reliable techniques to the detect signals of known structure and amplitude smaller than the level of the contaminating noise. Under the assumption of stationary Gaussian noise, MF maximizes the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA). This property relies upon a priori knowledge of the position of the searched signals, which is usually not available. Recently, it has been shown that when applied in its standard form, MF may severely underestimate the PFA. As a consequence the statistical significance of features that belong to noise is overestimated and the resulting detections are actually spurious. For this reason, an alternative method of computing the PFA has been proposed that is based on the Probability density function (PDF) of the peaks of an isotropic Gaussian random field. In this paper we further develop this method. In particular, we discuss the statistical meaning of the PFA and show that, although useful as a preliminary step in a detection procedure, it is not able to quantify the actual reliability of a specific detection. For this reason, a new quantity is introduced called the specific Probability of false alarm (SPFA), which is able to carry out this computation. We show how this method works in targeted simulations and apply it to a few interferometric maps taken with the Atacama Large Millimeter/submillimeter Array (ALMA) and the Australia Telescope Compact Array (ATCA). We select a few potential new point sources and assign an accurate detection reliability to these sources.
R Vio - One of the best experts on this subject based on the ideXlab platform.
-
the correct estimate of the Probability of false detection of the matched filter in weak signal detection problems iii peak distribution method versus the gumbel distribution method
Astronomy and Astrophysics, 2019Co-Authors: R Vio, P Andreani, A Biggs, N HayatsuAbstract:The matched filter (MF) represents one of the main tools to detect signals from known sources embedded in the noise. In the Gaussian case the noise is assumed to be the realization of a Gaussian random field (GRF). The most important property of the MF, the maximization of the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA), makes it one of the most popular techniques. However, the MF technique relies upon the a priori knowledge of the number and the position of the searched signals in the GRF which usually are not available. A typical way out is to assume that the position of a signal coincides with one of the peaks in the matched filtered data. A detection is claimed when the Probability that a given peak is due only to the noise (i.e. the PFA) is smaller than a prefixed threshold. In this case the Probability density function (PDF) of the amplitudes has to be used for the computation of the PFA, which is different from the Gaussian. Moreover, the Probability that a detection is false depends on the number of peaks present in the filtered GRF, the greater the number of peaks in a GRF, the higher the Probability of peaks due to the noise that exceed the detection threshold. If not taken into account, the PFA can be severely underestimated. Many solutions proposed to this problem are non-parametric hence not able to exploit all the available information. This limitation has been overcome by means of two efficient parametric approaches, one based on the PDF of the peak amplitudes of a smooth and isotropic GRF whereas the other uses the Gumbel distribution (the asymptotic PDF of the corresponding extreme). Simulations and ALMA maps show that, although the two methods produce almost identical results, the first is more flexible and allows us to check the reliability of the detection procedure.
-
correct estimate of the Probability of false detection of the matched filter in weak signal detection problems iii peak distribution method versus the gumbel distribution method
arXiv: Instrumentation and Methods for Astrophysics, 2019Co-Authors: R Vio, P Andreani, A Biggs, N HayatsuAbstract:The matched filter (MF) represents one of the main tools to detect signals from known sources embedded in the noise. In the Gaussian case the noise is assumed to be the realization of a Gaussian random field (GRF). The most important property of the MF, the maximization of the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA), makes it one of the most popular techniques. However, the MF technique relies upon the a priori knowledge of the number and the position of the searched signals in the GRF which usually are not available. A typical way out is to assume that the position of a signal coincides with one of the peaks in the matched filtered data. A detection is claimed when the Probability that a given peak is due only to the noise (i.e. the PFA) is smaller than a prefixed threshold. In this case the Probability density function (PDF) of the amplitudes has to be used for the computation of the PFA, which is different from the Gaussian. Moreover, the Probability that a detection is false depends on the number of peaks present in the filtered GRF, the greater the number of peaks in a GRF, the higher the Probability of peaks due to the noise that exceed the detection threshold. If not taken into account, the PFA can be severely underestimated. Many solutions proposed to this problem are non-parametric hence not able to exploit all the available information. This limitation has been overcome by means of two efficient parametric approaches, one based on the PDF of the peak amplitudes of a smooth and isotropic GRF whereas the other uses the Gumbel distribution (the asymptotic PDF of the corresponding extreme). Simulations and ALMA maps show that, although the two methods produce almost identical results, the first is more flexible and allows us to check the reliability of the detection procedure.
-
the correct estimate of the Probability of false detection of the matched filter in weak signal detection problems ii further results with application to a set of alma and atca data
Astronomy and Astrophysics, 2017Co-Authors: R Vio, C Verges, P AndreaniAbstract:The matched filter (MF) is one of the most popular and reliable techniques to the detect signals of known structure and amplitude smaller than the level of the contaminating noise. Under the assumption of stationary Gaussian noise, MF maximizes the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA). This property relies upon a priori knowledge of the position of the searched signals, which is usually not available. Recently, it has been shown that when applied in its standard form, MF may severely underestimate the PFA. As a consequence the statistical significance of features that belong to noise is overestimated and the resulting detections are actually spurious. For this reason, an alternative method of computing the PFA has been proposed that is based on the Probability density function (PDF) of the peaks of an isotropic Gaussian random field. In this paper we further develop this method. In particular, we discuss the statistical meaning of the PFA and show that, although useful as a preliminary step in a detection procedure, it is not able to quantify the actual reliability of a specific detection. For this reason, a new quantity is introduced called the specific Probability of false alarm (SPFA), which is able to carry out this computation. We show how this method works in targeted simulations and apply it to a few interferometric maps taken with the Atacama Large Millimeter/submillimeter Array (ALMA) and the Australia Telescope Compact Array (ATCA). We select a few potential new point sources and assign an accurate detection reliability to these sources.
-
the correct estimate of the Probability of false detection of the matched filter in the detection of weak signals ii further results with application to a set of alma and atca data
arXiv: Instrumentation and Methods for Astrophysics, 2017Co-Authors: R Vio, C Verges, P AndreaniAbstract:The matched filter (MF) is one of the most popular and reliable techniques to the detect signals of known structure and amplitude smaller than the level of the contaminating noise. Under the assumption of stationary Gaussian noise, MF maximizes the Probability of detection subject to a Constant Probability of false detection or false alarm (PFA). This property relies upon a priori knowledge of the position of the searched signals, which is usually not available. Recently, it has been shown that when applied in its standard form, MF may severely underestimate the PFA. As a consequence the statistical significance of features that belong to noise is overestimated and the resulting detections are actually spurious. For this reason, an alternative method of computing the PFA has been proposed that is based on the Probability density function (PDF) of the peaks of an isotropic Gaussian random field. In this paper we further develop this method. In particular, we discuss the statistical meaning of the PFA and show that, although useful as a preliminary step in a detection procedure, it is not able to quantify the actual reliability of a specific detection. For this reason, a new quantity is introduced called the specific Probability of false alarm (SPFA), which is able to carry out this computation. We show how this method works in targeted simulations and apply it to a few interferometric maps taken with the Atacama Large Millimeter/submillimeter Array (ALMA) and the Australia Telescope Compact Array (ATCA). We select a few potential new point sources and assign an accurate detection reliability to these sources.
Constantinos Daskalakis - One of the best experts on this subject based on the ideXlab platform.
-
species trees from gene trees despite a high rate of lateral genetic transfer a tight bound
Symposium on Discrete Algorithms, 2016Co-Authors: Constantinos Daskalakis, Sebastien RochAbstract:Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of lateral genetic transfer (LGT), whereby a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from (but related to) the species phylogeny. In previous work, a stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a Constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a Constant Probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching bound in the negative direction (up to a Constant).
-
species trees from gene trees despite a high rate of lateral genetic transfer a tight bound extended abstract
Symposium on Discrete Algorithms, 2016Co-Authors: Constantinos Daskalakis, Sebastien RochAbstract:Reconstructing the tree of life from molecular sequences is a fundamental problem in computational biology. Modern data sets often contain a large number of genes which can complicate the reconstruction problem due to the fact that different genes may undergo different evolutionary histories. This is the case in particular in the presence of lateral genetic transfer (LGT), whereby a gene is inherited from a distant species rather than an immediate ancestor. Such an event produces a gene tree which is distinct from (but related to) the species phylogeny. In previous work, a stochastic model of LGT was introduced and it was shown that the species phylogeny can be reconstructed from gene trees despite surprisingly high rates of LGT. Both lower and upper bounds on this rate were obtained, but a large gap remained. Here we close this gap, up to a Constant. Specifically, we show that the species phylogeny can be reconstructed perfectly even when each edge of the tree has a Constant Probability of being the location of an LGT event. Our new reconstruction algorithm builds the tree recursively from the leaves. We also provide a matching bound in the negative direction (up to a con-
David P Woodruff - One of the best experts on this subject based on the ideXlab platform.
-
an optimal algorithm for e 1 heavy hitters in insertion streams and related problems
ACM Transactions on Algorithms, 2019Co-Authors: Arnab Bhattacharyya, David P WoodruffAbstract:We give the first optimal bounds for returning the e1-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of m items in { 1, 2, … , n} and parameters 0 < e < p l 1, let fi denote the frequency of item i, i.e., the number of times item i occurs in the stream. With arbitrarily large Constant Probability, our algorithm returns all items i for which fi g p m, returns no items j for which fj l (p −e)m, and returns approximations f˜i with vf˜i − fiv l e m for each item i that it returns. Our algorithm uses O(e−1 log p −1 + p −1 log n + log log m) bits of space, processes each stream update in O(1) worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a Constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive e m error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of e1-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.
-
an optimal algorithm for l1 heavy hitters in insertion streams and related problems
arXiv: Data Structures and Algorithms, 2016Co-Authors: Arnab Bhattacharyya, David P WoodruffAbstract:We give the first optimal bounds for returning the $\ell_1$-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of $m$ items in $\{1, 2, \dots, n\}$ and parameters $0 < \epsilon < \phi \leq 1$, let $f_i$ denote the frequency of item $i$, i.e., the number of times item $i$ occurs in the stream. With arbitrarily large Constant Probability, our algorithm returns all items $i$ for which $f_i \geq \phi m$, returns no items $j$ for which $f_j \leq (\phi -\epsilon)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq \epsilon m$ for each item $i$ that it returns. Our algorithm uses $O(\epsilon^{-1} \log\phi^{-1} + \phi^{-1} \log n + \log \log m)$ bits of space, processes each stream update in $O(1)$ worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a Constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive $\epsilon m$ error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of $\ell_1$-heavy hitters. We also introduce several variants of the heavy hitters and maximum frequency problems, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings. Unlike the traditional heavy hitters problem, some of these variants look at comparisons between items rather than numerical values to determine the frequency of an item.
-
on sketching matrix norms and the top singular vector
Symposium on Discrete Algorithms, 2014Co-Authors: Yi Li, Huy L. Nguyễn, David P WoodruffAbstract:Sketching is a prominent algorithmic tool for processing large data. In this paper, we study the problem of sketching matrix norms. We consider two sketching models. The first is bilinear sketching, in which there is a distribution over pairs ofrxn matrices S and n x s matrices T such that for any fixed n x n matrix A, from S · A · T one can approximate ||A||p up to an approximation factor α ≥ 1 with Constant Probability, where ||A||p is a matrix norm. The second is general linear sketching, in which there is a distribution over linear maps L: Rn2 → Rk, such that for any fixed n x n matrix A, interpreting it as a vector in Rn2, from L(A) one can approximate ||A||p up to a factor α. We study some of the most frequently occurring matrix norms, which correspond to Schatten p-norms for p e {0, 1, 2, ∞}. The p-th Schatten norm of a rank-r matrix A is defined to be [EQUATION], where σ1,...,σr are the singular values of A. When p = 0, ||A||0 is defined to be the rank of A. The cases p = 1, 2, and ∞ correspond to the trace, Frobenius, and operator norms, respectively. For bilinear sketches we show: 1. For p = ∞ any sketch must have r · s = O(n2/α4) dimensions. This matches an upper bound of Andoni and Nguyen (SODA, 2013), and implies one cannot approximate the top right singular vector v of A by a vector v' with ||v' -- v||2 ≤ 1/2 with r · s = o(n2) 2. For p e {0, 1} and Constant α, any sketch must have r · s ≥ n1-e dimensions, for arbitrarily small Constant e > 0. 3. For even integers p ≥ 2, we give a sketch with r · s = O(n2-4/pe-2) dimensions for obtaining a (1 + e)-approximation. This is optimal up to logarithmic factors, and is the first general subquadratic upper bound for sketching the Schatten norms. For general linear sketches our results, though not optimal, are qualitatively similar, showing that for p = ∞, k = Ω(n3/2/α4) and for p e {0, 1}, k = Ω(√n). These give separations in the sketching complexity of Schatten-p norms with the corresponding vector p-norms, and rule out a table lookup nearest-neighbor search for p = 1, making progress on a question of Andoni.
-
a tight lower bound for high frequency moment estimation with small error
International Workshop and International Workshop on Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques, 2013Co-Authors: David P WoodruffAbstract:We show an Ω((n 1 − 2/p logM)/e 2) bits of space lower bound for (1 + e)-approximating the p-th frequency moment \(F_p = \|x\|_p^p = \sum_{i=1}^n |x_i|^p\) of a vector x ∈ { − M, − M + 1, …, M} n with Constant Probability in the turnstile model for data streams, for any p > 2 and e ≥ 1/n 1/p (we require e ≥ 1/n 1/p since there is a trivial O(n logM) upper bound). This lower bound matches the space complexity of an upper bound of Ganguly for any e 2 and e ≥ 1/n 1/p . This is again optimal for e < 1/log O(1) n.
-
lower bounds for sparse recovery
arXiv: Data Structures and Algorithms, 2011Co-Authors: Piotr Indyk, Eric Price, David P WoodruffAbstract:We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-sparse} x"} ||x-x"||_1. It is known that there exist matrices A with this property that have only O(k log (n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general /randomized/ version of the problem, where A is a random variable and the recovery algorithm is required to work for any fixed x with Constant Probability (over A).