Braxton Osting
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Braxton Osting has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Andrea Louise Bertozzi
Department of Mathematics UCLA 90095 Los Angeles CA
3 shared publications - Nestor Guillen
Texas State University University of Chicago
3 shared publications - Yves van Gennip
Delft University of Technology
3 shared publications - Chiu-Yen Kao
Department of Mathematical Sciences Claremont McKenna College 91711 CA
1 shared publication - Chris D. White
Department of Mathematics University of Texas at Austin 78712 Austin TX USA
1 shared publication Daniel Barrow
Pitzer College, Department of Mathematics, 1050 North Mills Avenue, Claremont, CA 91711, USA
1 shared publication
Latest Publications
- Open Access
Mean curvature, threshold dynamics, and phase field theory on finite graphs
In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples and identify open questions for future study. We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized, and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow. We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as "freezing" or "pinning") and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation.
Open AccessMean curvature, threshold dynamics, and phase field theory on finite graphs
In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples and identify open questions for future study. We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized, and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow. We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as "freezing" or "pinning") and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation.
- Open Access
Minimal Dirichlet energy partitions for graphs
Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreasing and converges in a finite number of iterations to a local minimum of the relaxed objective function. Our method is applied to several clustering problems on graphs constructed from synthetic data, MNIST handwritten digits, and manifold discretizations. The model has a semi-supervised extension and provides a natural representative for the clusters as well.
Open AccessMinimal Dirichlet energy partitions for graphs
Motivated by a geometric problem, we introduce a new non-convex graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. A relaxed formulation is identified and a novel rearrangement algorithm is proposed, which we show is strictly decreasing and converges in a finite number of iterations to a local minimum of the relaxed objective function. Our method is applied to several clustering problems on graphs constructed from synthetic data, MNIST handwritten digits, and manifold discretizations. The model has a semi-supervised extension and provides a natural representative for the clusters as well.
- Open Access
- 18 April 2014
- Published by Springer Nature in Milan Journal of Mathematics
- Vol. 82 (1) , 3-65
Mean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs
- 18 April 2014
- Published by Springer Nature in Milan Journal of Mathematics
- Vol. 82 (1) , 3-65
Open AccessMean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs
- 13 September 2013
- Published by Springer Nature in Applied Mathematics & Optimization
- Vol. 69 (1) , 123-139
Minimal Convex Combinations of Three Sequential Laplace-Dirichlet Eigenvalues
- 13 September 2013
- Published by Springer Nature in Applied Mathematics & Optimization
- Vol. 69 (1) , 123-139
Minimal Convex Combinations of Three Sequential Laplace-Dirichlet Eigenvalues
- 28 June 2013
- Published by Defense Technical Information Center (DTIC)
Mean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs
In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples, and identify open questions for future study. We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow. We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as freezing or pinning) and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation.
- 28 June 2013
- Published by Defense Technical Information Center (DTIC)
Mean Curvature, Threshold Dynamics, and Phase Field Theory on Finite Graphs
In the continuum, close connections exist between mean curvature flow, the Allen-Cahn (AC) partial differential equation, and the Merriman-Bence-Osher (MBO) threshold dynamics scheme. Graph analogues of these processes have recently seen a rise in popularity as relaxations of NP-complete combinatorial problems, which demands deeper theoretical underpinnings of the graph processes. The aim of this paper is to introduce these graph processes in the light of their continuum counterparts, provide some background, prove the first results connecting them, illustrate these processes with examples, and identify open questions for future study. We derive a graph curvature from the graph cut function, the natural graph counterpart of total variation (perimeter). This derivation and the resulting curvature definition differ from those in earlier literature, where the continuum mean curvature is simply discretized and bears many similarities to the continuum nonlocal curvature or nonlocal means formulation. This new graph curvature is not only relevant for graph MBO dynamics, but also appears in the variational formulation of a discrete time graph mean curvature flow. We prove estimates showing that the dynamics are trivial for both MBO and AC evolutions if the parameters (the time-step and diffuse interface scale, respectively) are sufficiently small (a phenomenon known as freezing or pinning) and also that the dynamics for MBO are nontrivial if the time step is large enough. These bounds are in terms of graph quantities such as the spectrum of the graph Laplacian and the graph curvature. Adapting a Lyapunov functional for the continuum MBO scheme to graphs, we prove that the graph MBO scheme converges to a stationary state in a finite number of iterations. Variations on this scheme have recently become popular in the literature as ways to minimize (continuum) nonlocal total variation.
- Open Access
- 1 January 2013
- Published by American Institute of Mathematical Sciences (AIMS) in Inverse Problems and Imaging
- Vol. 7 (3) , 907-926
Statistical ranking using the $l^{1}$-norm on graphs
We consider the problem of establishing a statistical ranking for a set of alternatives from a dataset which consists of an (inconsistent and incomplete) set of quantitative pairwise comparisons of the alternatives. If we consider the directed graph where vertices represent the alternatives and the pairwise comparison data is a function on the arcs, then the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential optimally agrees with the pairwise comparisons. Potentials, optimal in the $l^{2}$-norm sense, can be found by solving a least-squares problem on the digraph and, recently, the residual has been interpreted using the Hodge decomposition (Jiang et. al., 2010). In this work, we consider an $l^{1}$-norm formulation of the statistical ranking problem. We describe a fast graph-cut approach for finding $\epsilon$-optimal solutions, which has been used successfully in image processing and computer vision problems. Applying this method to several datasets, we demonstrate its efficacy at finding solutions with sparse residual.
- 1 January 2013
- Published by American Institute of Mathematical Sciences (AIMS) in Inverse Problems and Imaging
- Vol. 7 (3) , 907-926
Open AccessStatistical ranking using the $l^{1}$-norm on graphs
We consider the problem of establishing a statistical ranking for a set of alternatives from a dataset which consists of an (inconsistent and incomplete) set of quantitative pairwise comparisons of the alternatives. If we consider the directed graph where vertices represent the alternatives and the pairwise comparison data is a function on the arcs, then the statistical ranking problem is to find a potential function, defined on the vertices, such that the gradient of the potential optimally agrees with the pairwise comparisons. Potentials, optimal in the $l^{2}$-norm sense, can be found by solving a least-squares problem on the digraph and, recently, the residual has been interpreted using the Hodge decomposition (Jiang et. al., 2010). In this work, we consider an $l^{1}$-norm formulation of the statistical ranking problem. We describe a fast graph-cut approach for finding $\epsilon$-optimal solutions, which has been used successfully in image processing and computer vision problems. Applying this method to several datasets, we demonstrate its efficacy at finding solutions with sparse residual.
- 1 January 2013
- Published by Walter de Gruyter GmbH in Journal of Quantitative Analysis in Sports
- Vol. 9 (2) , 187-202
Ranking rankings: an empirical comparison of the predictive power of sports ranking methods
In this paper, we empirically evaluate the predictive power of eight sports ranking methods. For each ranking method, we implement two versions, one using only win-loss data and one utilizing score-differential data. The methods are compared on 4 datasets: 32 National Basketball Association (NBA) seasons, 112 Major League Baseball (MLB) seasons, 22 NCAA Division 1-A Basketball (NCAAB) seasons, and 56 NCAA Division 1-A Football (NCAAF) seasons. For each season of each dataset, we apply 20-fold cross validation to determine the predictive accuracy of the ranking methods. The non-parametric Friedman hypothesis test is used to assess whether the predictive errors for the considered rankings over the seasons are statistically dissimilar. The post-hoc Nemenyi test is then employed to determine which ranking methods have significant differences in predictive power. For all datasets, the null hypothesis – that all ranking methods are equivalent – is rejected at the 99% confidence level. For NCAAF and NCAAB datasets, the Nemenyi test concludes that the implementations utilizing score-differential data are usually more predictive than those using only win-loss data. For the NCAAF dataset, the least squares and random walker methods have significantly better predictive accuracy at the 95% confidence level than the other methods considered.
- 1 January 2013
- Published by Walter de Gruyter GmbH in Journal of Quantitative Analysis in Sports
- Vol. 9 (2) , 187-202
Ranking rankings: an empirical comparison of the predictive power of sports ranking methods
In this paper, we empirically evaluate the predictive power of eight sports ranking methods. For each ranking method, we implement two versions, one using only win-loss data and one utilizing score-differential data. The methods are compared on 4 datasets: 32 National Basketball Association (NBA) seasons, 112 Major League Baseball (MLB) seasons, 22 NCAA Division 1-A Basketball (NCAAB) seasons, and 56 NCAA Division 1-A Football (NCAAF) seasons. For each season of each dataset, we apply 20-fold cross validation to determine the predictive accuracy of the ranking methods. The non-parametric Friedman hypothesis test is used to assess whether the predictive errors for the considered rankings over the seasons are statistically dissimilar. The post-hoc Nemenyi test is then employed to determine which ranking methods have significant differences in predictive power. For all datasets, the null hypothesis – that all ranking methods are equivalent – is rejected at the 99% confidence level. For NCAAF and NCAAB datasets, the Nemenyi test concludes that the implementations utilizing score-differential data are usually more predictive than those using only win-loss data. For the NCAAF dataset, the least squares and random walker methods have significantly better predictive accuracy at the 95% confidence level than the other methods considered.