The CUNY Data Science and Applied Topology Reading Group is joint between the Mathematics and Computer Science programmes. We meet Fridays 11.45 -- 12.45 in GC 4419. You can contact us at firstname.lastname@example.org.
Our plan is to primarily read and discuss seminal papers in data science, in applied topology and in topological data analysis. Each seminar one participant takes the responsibility to present a paper and prepare items for discussion. We expect occasionally to be able to invite external speakers.
SEMINAR CANCELLED FOR SPRING 2020
With the fast developing situation around CUNY and NYCs reactions to the Coronavirus, we have decided to cancel the Data Science and Applied Topology seminar for the remainder of the spring semester 2020.
We expect to welcome you back for the fall seminar early September.
Current schedule can be found here.
We will be sending out announcements through a mailing list; you can subscribe here.
- Mikael Vejdemo-Johansson, Computer Science Programme, CUNY Graduate Center; Department of Mathematics, CUNY College of Staten Island
- Azita Mayeli, Mathematics Programme, CUNY Graduate Center; Department of Mathematics, CUNY Queensborough Community College
We have compiled a list of papers that might be interesting to present.
Multiplierless iteration for the resolution of semidefinite linear systems
Algorithms of numerical analysis assume by default that all numbers manipulated by the computer are real numbers. We introduce for the first time in this talk a numerical method that accommodates the internal coarse binary operations of a computer to increase the efficiency of the algorithm. We show that a linear system of equations with a matrix that is symmetric and positive semidefinite can be iteratively solved with an algorithm where every multiplication is reduced to a scaling by a power of 2, which simply amounts to bit shifts in binary.
We will then see how this multiplierless algorithm can be used in various problems, such as least squares, l1-regularized least squares and the minimal-norm resolution of any consistent linear system. A particular application of focus will be the minimal-norm reconstruction of a bandlimited signal from generalized nonuniform samples.
This seminar got cancelled.
Evasion and Coverage problems
An overview of previous work using topological methods to attack the coverage and the evasion problems.
Efficient call pricing model discovery by backpropagation through time
In this paper, we propose a novel call pricing model discovery method using the Heston model to find the set of parameter values that minimize the square loss between our model’s predictions and observed call prices given by market makers such as Jean Street or Two Sigma. The goal of this article is to formulate a stochastic optimization method for the Heston model over a certain period of time. The novelty of this paper is that we treat the Heston model as a Recurrent Neural Network and derive the Gradient of the Heston model by Backpropagation Through Time to reduce the computation time for obtaining the gradient from O(τ 2 ) to O(τ ). Further, to stabilize the gradient, we extend our method by adding min-batch method. To our best knowledge, this is the first paper to propose a SGD based Heston calibration method by min-batch extension. Our method minimizes the square loss twice more than model a trivial call pricing discovery method using the Black-Scholes-Merton model.
Treewidth and metric complexity for hyperbolic 3-manifolds
Treewidth is an invariant of graphs which measures how close a graph is to being a tree. A number of algorithms that are exponential over all graphs are polynomial over graphs of bounded tree width. The treewidth of a 3-manifold is the minimal treewidth of the dual graph of any triangulation of the manifold. A number of 3-manifold invariants which are exponential in the number of tetrahedra are polynomial for manifolds of bounded treewidth, for example, the Turaev-Viro invariants. We show that for hyperbolic 3-manifolds, treewidth is linearly related to a metric complexity defined in terms of Morse functions to trees. In particular, this shows that there are 3-manifolds of arbitrarily large treewidth. This is joint work with Diane Hoffoss.
Topology and Dynamics of Biological Networks
Complex networks have been of great interests in many disciplines including mathematics, computer science, biology, and social studies. In molecular biology, networks can be used to model the interacts within a biological system. Such a network often consists of units with various levels of activities that evolve over time, mathematically represented by the dynamics of the network. The interaction between units is represented by the topology of a graph. An interesting problem is to study the connection between topology and dynamics of such networks. In particular, the so called reverse engineering problem asks for the topology of the network given information on its dynamics.
In this talk, we focus on a certain Boolean network model for biological networks.
Under this model, the reverse engineering problem is naturally related to the
Satisfiability Problem. We will show the following results.
(1). The decision problem for network solution can be solved in polynomial time.
That is, given information on dynamics, there is a polynomial time algorithm that determines either (a) there is no network which yields the given dynamics or (b) there is such a network. In the case of (b), the algorithm provides a specific network solution. (2). The problem of finding a minimal network with the given property of dynamics is NP-hard.
Mostly monotone correlation
Super-resolution, subspace methods, and non-harmonic Fourier matrices
This talk is concerned with the super-resolution problem of recovering a discrete measure on the torus consisting of S atoms, given M consecutive noisy Fourier coefficients. Super-resolution recovery is sensitive to noise when the distance between two atoms is less than 1/M and many algorithms fail in this regime. In this talk, we connect this problem to the minimum singular value of non-harmonic Fourier matrices. New results for the latter are presented, and as consequences, we derive results regarding the super-resolution limit of subspace methods (namely, MUSIC and ESPRIT). These results rigorously establish the super-resolution phenomena of these algorithms that were empirically discovered long ago, and numerical results indicate that our bounds are sharp or nearly sharp. Information theoretic lower bounds imply that both algorithms are near optimal for super-resolution. Time permitting, we will discuss how to quantize the Fourier measurements using distributed beta encoding in order to minimize the reconstruction error using either convex or subspace methods. Joint work with Albert Fannjiang, Sinan Gunturk, and Wenjing Liao.