- You are here:
- GT Home
- Home
- News & Events

Series: Research Horizons Seminar

Hosted by: Huy Huynh and Yao Li

Sampling from and approximately counting the size of a large set

of combinatorial structures has contributed to a renaissance in research

in finite Markov chains in the last two decades.

Applications are wide-ranging from sophisticated card shuffles,

deciphering simple substitution ciphers (of

prison inmates in the California state prison), estimating the volume of

a high-dimensional convex body,

and to understanding the speed of Gibbs sampling heuristics in

statistical physics. More recent applications include rigorous estimates

on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the

discrete logarithm problem in finite cyclic groups.

The lecture will be a brief (mostly self-contained) introduction to the

Markov Chain Monte Carlo (MCMC) methodology and applications, and will

include some open problems.

of combinatorial structures has contributed to a renaissance in research

in finite Markov chains in the last two decades.

Applications are wide-ranging from sophisticated card shuffles,

deciphering simple substitution ciphers (of

prison inmates in the California state prison), estimating the volume of

a high-dimensional convex body,

and to understanding the speed of Gibbs sampling heuristics in

statistical physics. More recent applications include rigorous estimates

on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the

discrete logarithm problem in finite cyclic groups.

The lecture will be a brief (mostly self-contained) introduction to the

Markov Chain Monte Carlo (MCMC) methodology and applications, and will

include some open problems.

Monday, February 22, 2010 - 13:00 ,
Location: Skiles 255 ,
Heasoon Park ,
CSE, Georgia Institute of Technology ,
Organizer: Sung Ha Kang

Nonnegative Matrix

Factorization (NMF) has attracted much attention during the past

decade as a dimension reduction method in machine learning and data

analysis. NMF provides a lower rank approximation of a nonnegative

high dimensional matrix by factors whose elements are also

nonnegative. Numerous success stories were reported in application

areas including text clustering, computer vision, and cancer class

discovery.

Factorization (NMF) has attracted much attention during the past

decade as a dimension reduction method in machine learning and data

analysis. NMF provides a lower rank approximation of a nonnegative

high dimensional matrix by factors whose elements are also

nonnegative. Numerous success stories were reported in application

areas including text clustering, computer vision, and cancer class

discovery.

In

this talk, we present novel algorithms for NMF and NTF (nonnegative

tensor factorization) based on the alternating non-negativity

constrained least squares (ANLS) framework. Our new algorithm for NMF

is built upon the block principal pivoting method for the

non-negativity constrained least squares problem that overcomes some

limitations of the classical active set method. The proposed NMF

algorithm can naturally be extended to obtain highly efficient NTF

algorithm for PARAFAC (PARAllel FACtor) model. Our algorithms

inherit the convergence theory of the ANLS framework and can easily

be extended to other NMF formulations such as sparse NMF and NTF with

L1 norm constraints. Comparisons of algorithms using various data

sets show that the proposed new algorithms outperform existing ones

in computational speed as well as the solution quality.

This

is a joint work with Jingu Kim and Krishnakumar Balabusramanian.

Series: Analysis Working Seminar

We will start a discussion of arXiv:1001.4043, which characterizes the two weight inequality for the Hilbert transform, including the statement of the theorem, and some examples of how this question arises. Joint work with Ignacio Uriate-Tuero, and Eric Sawyer.

Series: Other Talks

The purpose of the Georgia Scientific Computing Symposium (GSC 2010) is to provide an opportunity for professors, postdocs and graduate students in the Atlanta area to meet in an informal setting, to exchange ideas, and to highlight local scientific computing research. The one-day symposium is open to the whole research community. The event is free but registration is required.

Series: Probability Working Seminar

In my talk, I will present the main results of a recent article by Martin Hairer and Jonathan Mattingly on an ergodic theorem for Markov chains. I will consider Markov chains evolving in discrete time on an abstract, possibly uncountable, state space. Under certain regularity assumptions on the chain's transition kernel, such as the existence of a Foster-Lyapunov function with small level sets (what exactly is meant by that will be thoroughly explained in the talk), one can establish the existence and uniqueness of a stationary distribution. I will focus on a new proof technique for that theorem which relies on a family of metrics on the set of probability measures living on the state space. The main result of my talk will be a strict contraction estimate involving these metrics.

Friday, February 19, 2010 - 14:00 ,
Location: Skiles 269 ,
Anh Tran ,
Georgia Tech ,
Organizer:

This is part 1 of a two part talk. The second part will continue next week.

I will introduce the AJ conjecture (by Garoufalidis)

which relates the A-polynomial and the colored Jones polynomial of a

knot in the 3-sphere. Then I will verify it for the trefoil and the

figure 8 knots (due to Garoufalidis) and torus knots (due to Hikami) by

explicit calculations.

which relates the A-polynomial and the colored Jones polynomial of a

knot in the 3-sphere. Then I will verify it for the trefoil and the

figure 8 knots (due to Garoufalidis) and torus knots (due to Hikami) by

explicit calculations.

Series: SIAM Student Seminar

This will be an introductory talk about Hardy inequalities. These inequalities are solutions to optimization problems, and their results are well-known. I will survey these results, and discuss some of the techniques used to solve these problems. The applications of Hardy inequalities are broad, from PDE's and mathematical physics to brownian motion. This talk will also serve as a lead-in to my talk at the Analysis seminar next Wednesday in which I discuss some current results that Michael Loss and I have obtained.

Series: School of Mathematics Colloquium

Let k be a p-adic field and K/k function field in one variable

over k. We discuss Hasse principle for existence of rational points

on homogeneous spaces under connected linear algebraic groups.

We illustrate how a positive answer to Hasse principle leads for instance to the result:

every quadratic form in nine variables over K has a nontrivial zero.

over k. We discuss Hasse principle for existence of rational points

on homogeneous spaces under connected linear algebraic groups.

We illustrate how a positive answer to Hasse principle leads for instance to the result:

every quadratic form in nine variables over K has a nontrivial zero.

Series: Graph Theory Seminar

A map is a connected graph G embedded in a surface S (a closed 2-manifold) such that all components of S -- G are simply connected regions. A map is rooted if an edge is distinguished together with a direction on the edge and a side of the edge. Maps have been enumerated by both mathematicians and physicists as they appear naturally in the study of representation theory, algebraic geometry, and quantum gravity. In 1986 Bender and Canfield showed that the number of n-edge rooted maps on an orientable surface of genus g is asymptotic to t_g n^{5(g-1)/2}12n^n, (n approaches infinity), where t_g is a positive constant depending only on g. Later it was shown that many families of maps satisfy similar asymptotic formulas in which tg appear as \universal constants". In 1993 Bender et al. derived an asymptotic formula for the num- ber of rooted maps on an orientable surface of genus g with i faces and j vertices. The formula involves a constant tg(r) (which plays the same role as tg), where r is determined by j=i.In this talk, we will review how these asymptotic formulas are obtained using Tutte's recursive approach. Connections with random trees, representation theory, integrable systems, Painleve I, and matrix integrals will also be mentioned. In particular, we will talk aboutour recent results about a simple relation between tg(r) and tg, and asymptotic formulas for the numbers of labeled graphs (of various connectivity)of a given genus. Similar results for non-orientable surfaces will also be discussed.

Series: ACO Colloquium

We establish the existence of scaling limits for several combinatorial optimization models on Erdos-Renyi and sparse random regular graphs. For a variety of models, including maximum independent sets, MAX-CUT, coloring and K-SAT, we prove that the optimal value appropriately rescaled, converges to a limit with high probability (w.h.p.), as the size of the underlying graph divergesto infinity. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. thus resolving an open problem. Our approach is based on developing a simple combinatorial approach to an interpolation method developed recently in the statistical physics literature. Among other things, theinterpolation method was used to prove the existence of the so-called free energy limits for several spin glass models including Viana-Bray and random K-SAT models. Our simpler combinatorial approach allows us to work with the zero temperature case (optimization) directly and extend the approach to many other models. Additionally, using our approach, we establish the large deviationsprinciple for the satisfiability property for constraint satisfaction problems such as coloring, K-SAT and NAE(Not-All-Equal)-K-SAT. The talk will be completely self-contained. No background on random graph theory/statistical physics is necessary. Joint work with Mohsen Bayati and Prasad Tetali