Brendan Ames
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
Research Subjects
Brendan Ames has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
Hristo S. Sendov
3 shared publications- Stephen A. Vavasis
Department of Combinatorics and Optimization Waterloo University of Waterloo N2L 3G1 Ontario Canada
3 shared publications - Gudmundur Einarsson
DeCODE genetics/AMGEN Inc., Reykjavik, Iceland
2 shared publications - Line Harder Clemmensen
Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark
2 shared publications - Mingyi Hong
University of Minnesota, Minneapolis, MN, USA
2 shared publications - Polina Bombina
Department of Mathematics, University of Alabama, Tuscaloosa, USA
2 shared publications
Latest Publications
- 21 December 2022
- Published by Springer Nature in Advances in Data Analysis and Classification
- Vol. 17 (4) , 983-1036
Proximal methods for sparse optimal scoring and discriminant analysis
- 21 December 2022
- Published by Springer Nature in Advances in Data Analysis and Classification
- Vol. 17 (4) , 983-1036
Proximal methods for sparse optimal scoring and discriminant analysis
- Open Access
Proximal Methods for Sparse Optimal Scoring and Discriminant Analysis
Linear discriminant analysis (LDA) is a classical method for dimensionality reduction, where discriminant vectors are sought to project data to a lower dimensional space for optimal separability of classes. Several recent papers have outlined strategies for exploiting sparsity for using LDA with high-dimensional data. However, many lack scalable methods for solution of the underlying optimization problems. We propose three new numerical optimization schemes for solving the sparse optimal scoring formulation of LDA based on block coordinate descent, the proximal gradient method, and the alternating direction method of multipliers. We show that the per-iteration cost of these methods scales linearly in the dimension of the data provided restricted regularization terms are employed, and cubically in the dimension of the data in the worst case. Furthermore, we establish that if our block coordinate descent framework generates convergent subsequences of iterates, then these subsequences converge to the stationary points of the sparse optimal scoring problem. We demonstrate the effectiveness of our new methods with empirical results for classification of Gaussian data and data sets drawn from benchmarking repositories, including time-series and multispectral X-ray data, and provide Matlab and R implementations of our optimization schemes.
Open AccessProximal Methods for Sparse Optimal Scoring and Discriminant Analysis
Linear discriminant analysis (LDA) is a classical method for dimensionality reduction, where discriminant vectors are sought to project data to a lower dimensional space for optimal separability of classes. Several recent papers have outlined strategies for exploiting sparsity for using LDA with high-dimensional data. However, many lack scalable methods for solution of the underlying optimization problems. We propose three new numerical optimization schemes for solving the sparse optimal scoring formulation of LDA based on block coordinate descent, the proximal gradient method, and the alternating direction method of multipliers. We show that the per-iteration cost of these methods scales linearly in the dimension of the data provided restricted regularization terms are employed, and cubically in the dimension of the data in the worst case. Furthermore, we establish that if our block coordinate descent framework generates convergent subsequences of iterates, then these subsequences converge to the stationary points of the sparse optimal scoring problem. We demonstrate the effectiveness of our new methods with empirical results for classification of Gaussian data and data sets drawn from benchmarking repositories, including time-series and multispectral X-ray data, and provide Matlab and R implementations of our optimization schemes.
- 11 September 2020
- Published by Springer Nature in Operations Research Forum
- Vol. 1 (3) , 1-24
Convex Optimization for the Densest Subgraph and Densest Submatrix Problems
- 11 September 2020
- Published by Springer Nature in Operations Research Forum
- Vol. 1 (3) , 1-24
Convex Optimization for the Densest Subgraph and Densest Submatrix Problems
- Open Access
Convex optimization for the densest subgraph and densest submatrix problems
We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum clique problem. We propose a new convex relaxation for the densest $k$-subgraph problem, based on a nuclear norm relaxation of a low-rank plus sparse decomposition of the adjacency matrices of $k$-node subgraphs to partially address this intractability. We establish that the densest $k$-subgraph can be recovered with high probability from the optimal solution of this convex relaxation if the input graph is randomly sampled from a distribution of random graphs constructed to contain an especially dense $k$-node subgraph with high probability. Specifically, the relaxation is exact when the edges of the input graph are added independently at random, with edges within a particular $k$-node subgraph added with higher probability than other edges in the graph. We provide a sufficient condition on the size of this subgraph $k$ and the expected density under which the optimal solution of the proposed relaxation recovers this $k$-node subgraph with high probability. Further, we propose a first-order method for solving this relaxation based on the alternating direction method of multipliers, and empirically confirm our predicted recovery thresholds using simulations involving randomly generated graphs, as well as graphs drawn from social and collaborative networks.Open AccessConvex optimization for the densest subgraph and densest submatrix problems
We consider the densest $k$-subgraph problem, which seeks to identify the $k$-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum clique problem. We propose a new convex relaxation for the densest $k$-subgraph problem, based on a nuclear norm relaxation of a low-rank plus sparse decomposition of the adjacency matrices of $k$-node subgraphs to partially address this intractability. We establish that the densest $k$-subgraph can be recovered with high probability from the optimal solution of this convex relaxation if the input graph is randomly sampled from a distribution of random graphs constructed to contain an especially dense $k$-node subgraph with high probability. Specifically, the relaxation is exact when the edges of the input graph are added independently at random, with edges within a particular $k$-node subgraph added with higher probability than other edges in the graph. We provide a sufficient condition on the size of this subgraph $k$ and the expected density under which the optimal solution of the proposed relaxation recovers this $k$-node subgraph with high probability. Further, we propose a first-order method for solving this relaxation based on the alternating direction method of multipliers, and empirically confirm our predicted recovery thresholds using simulations involving randomly generated graphs, as well as graphs drawn from social and collaborative networks. - Open Access
Exact Clustering of Weighted Graphs via Semidefinite Programming
As a model problem for clustering, we consider the densest k-disjoint-clique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of k large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of outliers. Further, we establish that if noise is weakly obscuring these clusters, i.e, the between-cluster edges are assigned very small weights, then we can recover significantly smaller clusters. For example, we show that in approximately sparse graphs, where the between-cluster weights tend to zero as the size n of the graph tends to infinity, we can recover clusters of size polylogarithmic in n. Empirical evidence from numerical simulations is also provided to support these theoretical phase transitions to perfect recovery of the cluster structure.
Open AccessExact Clustering of Weighted Graphs via Semidefinite Programming
As a model problem for clustering, we consider the densest k-disjoint-clique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite relaxation with high probability if the input graph is sampled from a distribution of clusterable graphs. Specifically, the semidefinite relaxation is exact if the graph consists of k large disjoint subgraphs, corresponding to clusters, with weight concentrated within these subgraphs, plus a moderate number of outliers. Further, we establish that if noise is weakly obscuring these clusters, i.e, the between-cluster edges are assigned very small weights, then we can recover significantly smaller clusters. For example, we show that in approximately sparse graphs, where the between-cluster weights tend to zero as the size n of the graph tends to infinity, we can recover clusters of size polylogarithmic in n. Empirical evidence from numerical simulations is also provided to support these theoretical phase transitions to perfect recovery of the cluster structure.
- 12 February 2016
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 64 (3) , 725-754
Alternating direction method of multipliers for penalized zero-variance discriminant analysis
- 12 February 2016
- Published by Springer Nature in Computational Optimization and Applications
- Vol. 64 (3) , 725-754
Alternating direction method of multipliers for penalized zero-variance discriminant analysis
- 1 January 2016
- Published by Elsevier in Journal of Mathematical Analysis and Applications
- Vol. 433 (2) , 1459-1485
Derivatives of compound matrix valued functions
- 1 January 2016
- Published by Elsevier in Journal of Mathematical Analysis and Applications
- Vol. 433 (2) , 1459-1485
Derivatives of compound matrix valued functions
- Open Access
Alternating direction method of multipliers for penalized zero-variance discriminant analysis
We consider the task of classification in the high dimensional setting where the number of features of the given data is significantly greater than the number of observations. To accomplish this task, we propose a heuristic, called sparse zero-variance discriminant analysis (SZVD), for simultaneously performing linear discriminant analysis and feature selection on high dimensional data. This method combines classical zero-variance discriminant analysis, where discriminant vectors are identified in the null space of the sample within-class covariance matrix, with penalization applied to induce sparse structures in the resulting vectors. To approximately solve the resulting nonconvex problem, we develop a simple algorithm based on the alternating direction method of multipliers. Further, we show that this algorithm is applicable to a larger class of penalized generalized eigenvalue problems, including a particular relaxation of the sparse principal component analysis problem. Finally, we establish theoretical guarantees for convergence of our algorithm to stationary points of the original nonconvex problem, and empirically demonstrate the effectiveness of our heuristic for classifying simulated data and data drawn from applications in time-series classification.
Open AccessAlternating direction method of multipliers for penalized zero-variance discriminant analysis
We consider the task of classification in the high dimensional setting where the number of features of the given data is significantly greater than the number of observations. To accomplish this task, we propose a heuristic, called sparse zero-variance discriminant analysis (SZVD), for simultaneously performing linear discriminant analysis and feature selection on high dimensional data. This method combines classical zero-variance discriminant analysis, where discriminant vectors are identified in the null space of the sample within-class covariance matrix, with penalization applied to induce sparse structures in the resulting vectors. To approximately solve the resulting nonconvex problem, we develop a simple algorithm based on the alternating direction method of multipliers. Further, we show that this algorithm is applicable to a larger class of penalized generalized eigenvalue problems, including a particular relaxation of the sparse principal component analysis problem. Finally, we establish theoretical guarantees for convergence of our algorithm to stationary points of the original nonconvex problem, and empirically demonstrate the effectiveness of our heuristic for classifying simulated data and data drawn from applications in time-series classification.
- 7 July 2015
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 167 (2) , 653-675
Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation
- 7 July 2015
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 167 (2) , 653-675
Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation
- 1 June 2015
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 25 (02) , 77-100
A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment
- 1 June 2015
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 25 (02) , 77-100
A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment