Colloquiums and Public Lectures 2017

Title: Sparse and Low-rank Tensor Estimation via Cubic Sketching
Speaker:Professor Guang Cheng
Date:28 November 2017 
Time:2.00pm - 3.00pm 
Venue:LT 4, (SPMS-03-09)
Host:Associate Professor Pan Guangming, Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: In this talk, we propose a general framework for sparse and low-rank tensor recovery from rank-one cubic sketchings. Two related statistical problems are covered by symmetric and non-symmetric models. One is high-dimensional linear regression model with interaction effect. Another one is statistical compressed image transmission. A block-wise thresholding gradient decent algorithm is proposed for stable recovery in both noiseless and noisy cases. Both upper bound and lower bound for the estimation accuracy are obtained over a large class of low-rank tensors, which show the optimality of the proposed procedure. To overcome the theoretical difficulty from high-order sub-Gaussian random variables, we also develop some novel tensor concentration inequalities, which may be of independent interests.

 

Title: Progress in Error-Correction: A Survey
Speaker:Visiting Professor Venkatesan Guruswami 
Date:22 September 2017
Time:1.30pm - 2.30pm
Venue:LT 5, (SPMS-03-08)
Host:Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: Error-correcting codes play a crucial role in safeguarding data against the adverse effects of noise during communication and storage. They are also versatile tools in the arsenal of theoretical computer science and combinatorics. The central challenge in coding theory is to construct codes with minimum possible redundancy for different error models and requirements on the decoder, along with efficient algorithms for error-correction using those codes. Much progress has been made toward this quest in the nearly seven decades since the birth of coding theory. Several fundamental problems, however, are still outstanding, and exciting new directions continue to emerge to address current technological demands as well as connections to computational complexity and cryptography.

This talk will survey some of our works over the years on error-correction in various models, such as:
- Worst-case errors, where we construct list decodable codes with redundancy as small as the target error fraction;
- i.i.d. errors, where we show polar codes enable efficient error-correction even as the redundancy approaches Shannon capacity;
- bit deletions, where we give codes that can correct the largest known fraction of deletions;
- Single symbol erasure, a model of renewed importance for tackling node failures in distributed storage, where we give novel repair algorithms for Reed-Solomon codes.

 

Title: Identities
Speaker:Professor Bruce C. Berndt
Date:31 May 2017
Time:11.00am - 12.00pm
Venue:LT 5, (SPMS-03-08)
Host:Associate Professor Chan Song Heng,
Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: 
As the title suggests, this lecture features mathematical identities. The identities we have chosen (we hope) are interesting, fascinating, surprising, and beautiful! Many of the identities are due to Ramanujan. Topics behind the identities include partitions, continued fractions, sums of squares, theta functions, Bessel functions, q-series, other infinite series, and infinite integrals.

 

Title: Intersecting families of permutations and perfect matchings
Speaker:Dr Ku Cheng Yeaw 
Date:21 April 2017
Time:1.30pm - 2.30pm
Venue:LT 5, (SPMS-03-08)
Host:Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: 

 

Title: Sketching as a Tool for Linear Algebra
Speaker:Dr David Woodruff 
Date:10 March 2017
Time:
1.30pm - 2.30pm
Venue:LT 5, (SPMS-03-08)
Host:Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: We give near optimal algorithms for regression, low rank approximation, and robust variants of these problems. Our results are based on the sketch and solve paradigm, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then run a slow algorithm on the smaller problem. These lead to the fastest known algorithms for fundamental machine learning and numerical linear algebra problems, which run in time proportional to the number of non-zero entries of the input. We first give algorithms for least squares regression, and robust variants such as l_p regression and M-Estimator loss functions. Then we give algorithms for approximate singular value decomposition, and robust variants such as minimizing sum of distances to a subspace, rather than sum of squared distances, as well as minimizing entrywise l_1-distance, etc.

 

Title: Topological modeling and analysis of complex data in biomolecules
Speaker:Assistant Professor Xia Kelin 
Date:3 February 2017
Time:1.15pm - 2.15pm
Venue:LT 5, (SPMS-03-08), School of Physical and Mathematical Sciences
Host:Division of Mathematical Sciences, School of Physical and Mathematical Sciences
Abstract: The understanding of biomolecular structure, flexibility, function, and dynamics is one of the most challenging tasks in biological science. We introduce persistent homology for extracting molecular topological fingerprints (MTFs) based on the persistence of molecular topological invariants. MTFs are utilized for protein characterization, identification, and classification. The multidimensional persistent homology is proposed and further used to quantitatively predict the stability of protein folding configurations generated by steered molecular dynamics. An excellent consistence between my persistent homology prediction and molecular dynamics simulation is found. Further, we introduce multiresolution persistent homology to handle complex biomolecular data. By appropriately tuning the resolution of a density function, we are able to focus the topological lens on the scale of interest. The proposed multiresolution -topological method has potential applications in arbitrary data sets, such as social networks, biological networks and graphs.