IDeAS
Fall 2017
IDeAS Seminar: Towards demystification of deep learning: function space analysis of the representation layersSpeaker: Shai Dekel, Tel Aviv University Date: Sep 19 2017  2:30pm Event type: IDeAS Room: McDonnell Hall, Room 102A Abstract: We propose a function space approach to Representation Learning [1] and the analysis of the representation layers in deep learning architectures. We show how to compute a `weaktype' Besov smoothness index that quantifies the geometry of the clustering in the feature space. This approach was already applied successfully to improve the performance of machine learning algorithms such as the Random Forest [2] and treebased Gradient Boosting [3]. Our experiments demonstrate that in wellknown and wellperforming trained networks, the Besov smoothness of the training set, measured in the corresponding hidden layer feature map representation, increases from layer to layer which relates to the `unfolding' of the clustering in the feature space. We also contribute to the understanding of generalization [4] by showing how the Besov smoothness of the representations, decreases as we add more mislabeling to the training data. We hope this approach will contribute to the demystification of some aspects of deep learning. References: [1] Y. Bengio , A. Courville and P. Vincenty, Representation Learning: A Review and New Perspectives, IEEE Transactions on Pattern Analysis and Machine Intelligence 8 (2013), 17981828. [2] O. Elisha and S. Dekel , Wavelet decompositions of Random Forests  smoothness analysis,sparse approximation and applications, Journal of machine learning research 17 (2016), 138. [3] S. Dekel, O. Elisha and O. Morgan, Wavelet decomposition of Gradient Boosting, preprint. [4] C. Zhang, S. Bengio, M. Hardt, B. Recht and O. Vinyals, Understanding deep learning requires rethinking generalization, In ICLR 2017 conference proceedings. Shai serves as Head of AI at WIX and is a visiting associate professor at the school of mathematical sciences at TelAviv University. For further information see: https://www.shaidekel.com/ 
IDeAS Seminar: Stability of some superresolution problemsSpeaker: Dmitry Batenkov, MIT Date: Sep 27 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: The problem of computational superresolution asks to recover an object from its noisy and limited spectrum. In this talk, we consider two inverse problems of this flavor, mainly from the point of view of stability estimates. In the first problem, we assume that the object's spectrum is a finite sum of exponentials modulated by polynomials (extending the wellresearched case where the polynomials are constants). We derive upper bounds on the problem condition number and show that the attainable resolution exhibits Höldertype continuity with respect to the noise level [1,3]. As an application we consider the approximation of a piecewisesmooth function from its Fourier coefficients. We can show that the asymptotic accuracy of our approach is only dictated by the smoothness of the function between the jumps, even if the jump locations are not known [2]. The second problem is concerned with ongoing work on the weighted extrapolation problem on the real line for functions of finite exponential type where we abandon the sparsity assumption. It turns out that the extrapolation range scales logarithmically with the noise level, while the pointwise extrapolation error exhibits again a Höldertype continuity. References: [1] A. Akinshin, D. Batenkov, and Y. Yomdin, “Accuracy of spiketrain Fourier reconstruction for colliding nodes,” in 2015 International Conference on Sampling Theory and Applications (SampTA), 2015, pp. 617–621. [2] D. Batenkov, “Complete algebraic reconstruction of piecewisesmooth functions from Fourier data,” Math. Comp., vol. 84, no. 295, pp. 2329–2350, 2015 [3] D. Batenkov, “Stability and superresolution of generalized spike recovery,” Applied and Computational Harmonic Analysis, http://dx.doi.org/10.1016/j.acha.2016.09.004. Dmitry Batenkov is a postdoctoral researcher at the Massachusetts Institute of Technology. His research interests include applied harmonic analysis, approximation theory, numerical analysis, sparse representations, sampling theory and inverse problems. http://dimabatenkov.info

IDeAS Seminar: When does an algorithm become a legitimate subject of study?Speaker: Veit Elser, Cornell University Date: Oct 11 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: Suppose you want to solve a combinatorially hard problem. Option one is to think really hard about the problem and design an algorithm that guarantees a solution. A second option is to try a “mystery” algorithm that comes without any guarantee of success but in practice usually outperforms any of the algorithms you have designed. Is there a point when you should shift your focus of study to the mystery algorithm? Does the mystery algorithm know something that you do not? This talk explores the questions above for the case of hard feasibility problems that are efficiently solved by iterated maps generated by projections to nonconvex sets. There is a strong analogy with mechanics. When applied to unfeasible instances these iterated maps sample a probability density in a high dimensional space, analogous to the attractor of a strongly mixing dynamical system. It is in this sense that the iterated map performs an exhaustive search. Feasible instances differ only in the existence of an attractive fixed point at some unknown location on the attractor. To improve the iteratedmap algorithm, one can dramatically increase the rate of discovery of the solution fixed point by reducing the KolmogorovSinai entropy of the attractor. These ideas will be illustrated with three applications: bit retrieval (phase retrieval on 2valued sequences), latinsquare completion and graph coloring. 
IDeAS Seminar: On multidimensional compact solitary patternsSpeaker: Philip Rosenau, Tel Aviv University Date: Oct 17 2017  2:30pm Event type: IDeAS Room: McDonnell Hall, Room 102A Abstract: As though to compensate for the rarity of multidimensional integrable systems in higher dimensions, spatial extensions of many of the wellknown nonlinear dispersive equations on the line, exhibit a remarkably rich variety of solitary patterns unavailable in 1D. Our work systematizes this observation with a special attention paid to compactons  solitary waves with compact support  where this effect is found to be far more pronounced and begets a zoo of multidimensional compact solitary patterns. One manifestation of this phenomenon is found in the sublinear NLS and Complex KleinGordon where the compactons inducing mechanism coupled with azimuthal spinning may expel the compact vortices from the origin to form a finite or countable number of genuine ringvortices. Such rings are an exclusive feature of compacton supporting systems. 
IDeAS Seminar: Iron Age Hebrew Epigraphy in the Silicon Age  An Algorithmic Approach To Study PaleoHebrew InscriptionsSpeaker: Barak Sober, Tel Aviv University Date: Oct 18 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: Handwriting comparison and identification, e.g. in the setting of forensics, has been widely addressed over the years. However, even in the case of modern documents, the proposed computerized solutions are quite unsatisfactory. For historical documents, such problems are worsened, due to the inscriptions’ preservation conditions. In the following lecture, we will present an attempt at addressing such a problem in the setting of First Temple Period inscriptions, stemming from the isolated military outpost of Arad (ca. 600 BCE). The solution we propose comprises: (A) Acquiring better imagery of the inscriptions using multispectral techniques; (B) Restoring characters via approximation of their composing strokes, represented as a splinebased structure, and estimated by an optimization procedure; (C) Feature extraction and distance calculation  creation of feature vectors describing various aspects of a specific character based upon its deviation from all other characters; (D) Conducting an experiment to test a null hypothesis that two given inscriptions were written by the same author. Applying this approach to the Arad corpus of inscriptions resulted in: (i) The discovery of a brand new inscription on the back side of a well known inscription (half a century after being unearthed); (ii) Empirical evidence regarding the literacy rates in the Kingdom of Judah on the eve of its destruction by Nebuchadnezzar the Babylonian king. Barak Sober received his B.Sc. degree in Mathematics and Philosophy from Tel Aviv University, Israel, in 2006. He received his M.Sc. in Applied Mathematics (summa cum laude) on the topic of “Handwritten Character Stroke Reconstruction” in 2013. He is currently pursuing his PhD in Applied Mathematics on the topic of “Approximation of Manifolds from Scattered Data”. His interests include approximation theory, machine learning, image processing and archaeology. 
IDeAS Seminar: Graphbased Bayesian learning: continuum limits and scalability of sampling algorithms.Speaker: Nicolas Garcia Trillos, Brown University Date: Oct 25 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: The principled learning of functions from data is at the core of statistics, machine learning and artificial intelligence. In this talk I will focus on Bayesian approaches to learning in the context of inverse problems on unknown domains and in particular to semisupervised learning. More specifically, we consider the problem of recovering a function input of a partial differential equation formulated on an unknown domain M where we can define a groundtruth Bayesian inverse problem. We assume to have access to a discrete domain Mn = {x1, . . . , xn} ⊂ M, and to noisy measurements of the output solution at p ≤ n of those points. The discrete domain is then endowed with a graph structure which is used to create a graph surrogate for the groundtruth Bayesian inverse problem. The first theoretical result that I will present establishes the convergence of the graph posterior distribution associated to the graphBayesian inverse problem towards its groundtruth counterpart as the number of unlabeled data points converges to infinity. Our analysis relies on the variational description of posterior distributions, the choice of an appropriate topology to compare distributions on different domains, and precise quantitative estimates of the spectrum of graph Laplacians. I will then show that our consistency results have profound algorithmic implications: when they hold, carefully designed graphbased Markov chain Monte Carlo (MCMC) algorithms have a uniform spectral gap, independent of the number of unlabeled data. This talk is based on works with Zachary Kaplan, Thabo Samakhoana, and Daniel SanzAlonso. 
IDeAS Seminar: Provably good convex methods for mapping problemsSpeaker: Nadav Dym, Weizmann Institute Date: Nov 8 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: Computing mappings or correspondences between surfaces is an important tool for many applications in computer graphics, computer vision, medical imaging, morphology and related fields. Mappings of least angle distortion (conformal) and distance distortion (isometric) are of particular interest. The problem of finding conformal/isometric mappings between surfaces is typically formulated as a difficult nonconvex optimization problem. Convex methods relax the nonconvex optimization problem to a convex problem which can then be solved globally. The main issue then is whether the global solution of the convex problem is a good approximation for the original global solution. In this talk we will discuss two families of convex relaxations. Conformal: We relax the problem of computing planar conformal mappings (Riemann mappings) to a simple convex problem which can be solved by solving a system of linear equations. We show that in this case the relaxation is exact the solution of the convex problem is guaranteed to be the Riemann mapping! Discrete isometric: for perfectly isometric asymmetric surfaces, the well known doublystochastic (DS) relaxation is exact. We generalize this result to the more challenging and important case of symmetric surfaces, once exactness is correctly defined for such problems. For nonisometric surfaces it is difficult to achieve exactness. Several relaxations have been proposed for such problems, where the more accurate relaxations are generally also more time consuming. We will describe two algorithm which strike a good balance between accuracy and efficiency: The DS++ algorithm, which is provably better than several popular algorithms but does not compromise efficiency, and the SinkhornJA algorithm, which gives a firstorder algorithm for efficiently solving the strong but highdimensional JA relaxation. We utilize this algorithmic improvement to achieve state of the art results for shape matching and image arrangement. Nadav Dym received his Bsc and Msc degrees in mathematics from the Hebrew University. His Msc thesis was on the topic “spatial recurrence for ergodic fractal measures “. He is currently pursuing his PhD degree in the department of computer science and applied mathematics in the Weizmann Institute, on the topic “convex methods for shape matching and related problems“ . His research interests include convex optimization, analysis and geometry and their applications. 
IDeAS Seminar: Computational Algebraic Geometry and Applications to Computer VisionSpeaker: Joe Kileel, Princeton University Date: Nov 15 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: Many models in science and engineering are described by polynomials. Computational algebraic geometry gives tools to analyze and exploit algebraic structure. In this talk, we offer a userfriendly introduction to some of these notions, including dimension (formalizing degrees of freedom), degree (formalizing the number of solutions to a polynomial system) and 01 laws in algebraic geometry (solution sets to polynomial systems exhibit similar behavior for all but a measure 0 subset of problem instances). We will also mention algorithms, based on Gröbner bases (symbolic techniques) and homotopy continuation (numerical techniques). Applied examples are drawn from the structurefrommotion problem in computer vision, where the task of building a 3D model from multiple 2D images leads to nontrivial polynomial systems. References include: J. Kileel, Minimal Problems for the Calibrated Trifocal Variety, SIAM Journal on Applied Algebra and Geometry 1 (2017) 575598. J. Kileel, Z. Kukelova, T. Pajdla and B. Sturmfels, Distortion Varieties, Foundations of Computational Mathematics, first online.
BIO: Joe Kileel is a postdoctoral research associate at Princeton’s Program in Applied and Computational Mathematics, and a member of the Simons Collaboration on Algorithms and Geometry. He received his PhD in May 2017 from UC Berkeley, advised by Bernd Sturmfels, where his thesis was awarded the Bernard Friedman Memorial Prize for best in applied mathematics. Joe's current publication list is available at http://web.math.princeton.edu/~jkileel/. 
IDeAS Seminar: Datadriven analysis of neuronal activitySpeaker: Gal Mishne, Yale University Date: Nov 29 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: Recent advances in experimental methods in neuroscience enable the acquisition of largescale, highdimensional and highresolution datasets. These complex and rich datasets call for the development of advanced data analysis tools, as commonly used techniques do not suffice to capture the spatiotemporal network complexity. In this talk I will present new datadriven methods based on global and local spectral embeddings for the processing and organization of highdimensional datasets, and demonstrate their application to the analysis of neuronal measurements. We develop a new greedy adaptive spectral clustering method capable of handling overlapping clusters and disregarding clutter. Applied to invivo calcium imaging of neurons and apical dendrites, we extract hundreds of neuronal structures with detailed morphology, and demixed and denoised timetraces. Next we introduce a nonlinear, datadriven and modelfree approach for the analysis of a spatiotemporal dynamical system, represented as a rank3 tensor. Applying our methodology to neuronal measurements, we identify, solely from observations and in a purely unsupervised datadriven manner, functional subsets of neurons, activity patterns associated with particular behaviors and pathological dysfunction caused by external intervention. Gal Mishne is a Gibbs Assistant Professor in the Applied Math program at Yale University, working with Ronald Coifman's research group. She completed her Ph.D. at the Viterbi Faculty of Electrical Engineering at the Technion in 2017, and holds a B.Sc. (summa cum laude) in Electrical Engineering and Physics from the Technion. Her research interests are highdimensional data analysis methods based on manifold learning and diffusion geometry for computational neuroscience, image processing and biomedical signal processing. 
IDeAS Seminar: Reconstructing 3D protein crystal intensity from unoriented sparse diffraction patternsSpeaker: TiYen Lan, Cornell University Date: Dec 6 2017  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: The femtoseconds long pulses of an Xray free electron laser (XFEL) enable the measurement to outrun the irreversible radiation damage. This concept of `diffract before destroy’ inspires new methods such as serial crystallography, which determines 3D protein structures by merging 2D snapshots of microcrystals collected at random orientations. In recent years, there has been a growing interest to apply this technique to the synchrotron storage ring sources because of their wider availability. For very small crystals, however, radiation damage occurs before sufficient numbers of photons are diffracted to determine the orientation of the crystal. The challenge is to merge data from a large number of such “sparse” frames in order to measure the full reciprocal space intensity. In this talk I will discuss our effort to develop an analysis method to analyze the unoriented sparse crystal diffraction patterns. Using the EMC algorithm (Loh & Elser, 2009), we reconstruct the 3D crystal intensity by iteratively maximizing the likelihood function of the crystal orientations. I will demonstrate the ability of our method to analyze sparse patterns through a couple of proofofconcept experiments with increasing complexity. Finally I will present our recent progress in applying the EMC algorithm to a serial crystallography dataset taken at a storage ring source. TiYen Lan received his B.S. degree in Physics from National Taiwan University, Taiwan, in 2012. He is now a Ph.D. candidate in Theoretical Physics working with Professor Veit Elser at Cornell University. He is interested in developing methods to extract information from noisy image data through the modeling of the image formation process. 
IDeAS SeminarSpeaker: Mahdi Soltanolkotabi, University of Southern California (USC) Date: Mar 14 2018  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: TBA 
IDeAS SeminarSpeaker: Jeffrey Donatelli, UC Berkeley Date: Apr 25 2018  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: TBA 
IDeAs SeminarSpeaker: Peter Doerschuk, Cornell University Date: May 2 2018  2:30pm Event type: IDeAS Room: 224 Fine Hall Abstract: TBA 