Fall 2014 Calendar

Octo­ber 14
Annie Ray­mond, Depart­ment of Math­e­mat­ics, UW.
A New Con­jec­ture for Union-Closed Families

Octo­ber 28
Jonathan Hauen­stein, Depart­ment of Applied and Com­pu­ta­tional Math­e­mat­ics and Sta­tis­tics, Uni­ver­sity of Notre Dame.
Opti­miza­tion and Numer­i­cal Alge­braic Geometry

Novem­ber 18
Daniela Wit­ten, Depart­ment of Bio­sta­tis­tics, UW.

Novem­ber 20 (Thurs­day)
Henry Wolkow­icz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.

Novem­ber 25
Emily Fox, Depart­ment of Sta­tis­tics, UW.

Decem­ber 2 [COREEEB125]
Peter Bür­gisser, Insti­tute for Math­e­mat­ics, TU Berlin.

Jan­u­ary 13 [CORE]
James Rene­gar, School of Oper­a­tions Research and Infor­ma­tion Engi­neer­ing, Cor­nell.

April 28 [CORE]
Joel Tropp, Depart­ment of Com­put­ing and Math­e­mat­i­cal Sci­ences, Cal­tech.

Click on the title or see below for the abstracts.

Jonathan Hauenstein; Opti­miza­tion and Numer­i­cal Alge­braic Geometry

Octo­ber 28, 2014, 4:00pm
GUG 204
Jonathan Hauen­stein, Depart­ment of Applied and Com­pu­ta­tional Math­e­mat­ics and Sta­tis­tics, Uni­ver­sity of Notre Dame.
Opti­miza­tion and Numer­i­cal Alge­braic Geometry

Abstract: Clas­si­cally, one can observe the com­bi­na­tion of alge­braic geom­e­try and opti­miza­tion in solv­ing poly­no­mial sys­tems con­structed from nec­es­sary con­di­tion of poly­no­mial opti­miza­tion prob­lems. More recently, the con­nec­tion between semi­def­i­nite pro­gram­ming and real alge­braic geom­e­try has been exploited. This talk will explore another use of opti­miza­tion related to alge­braic geom­e­try, namely to con­struct homo­topies in numer­i­cal alge­braic geom­e­try for solv­ing poly­no­mial sys­tems. This idea has been used recently to solve a prob­lem in real enu­mer­a­tive geom­e­try. This talk will con­clude with using alge­braic geom­e­try to solve sparse opti­miza­tion prob­lems aris­ing from the con­cept of matrix rigid­ity. To incor­po­rate a broad audi­ence, all nec­es­sary con­cepts related to alge­braic geom­e­try and homo­topies will be covered.

Annie Ray­mond; A New Conjecture for Union-Closed Families

Octo­ber 14, 2014, 4:00pm
GUG 204
Annie Ray­mond, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Wash­ing­ton.
A New Con­jec­ture for Union-Closed Families

Abstract: The Frankl union-closed sets con­jec­ture states that there exists an ele­ment present in at least half of the sets form­ing a union-closed fam­ily. We refor­mu­late the con­jec­ture as an opti­miza­tion prob­lem and present an inte­ger pro­gram to model it. The com­pu­ta­tions done with this pro­gram lead to a new con­jec­ture: we claim that the max­i­mum num­ber of sets in a non-empty union-closed fam­ily in which each ele­ment is present at most a times is inde­pen­dent of the num­ber n of ele­ments spanned by the sets if n is greater or equal to log_2(a)+1. We prove that this is true when n is greater or equal to a. We also dis­cuss the impact that this new con­jec­ture would have on the Frankl con­jec­ture if it turns out to be true. This is joint work with Jonad Pulaj and Dirk Theis.

Elina Robeva; Fixed Points of the EM Algorithm and Nonnegative Rank Boundaries

May 27, 2014, 4:00pm
EEB 303
Elina Robeva, Depart­ment of Math­e­mat­ics, UC Berke­ley.
Fixed Points of the EM Algo­rithm and Non­neg­a­tive Rank Boundaries

Abstract: Matri­ces of non­neg­a­tive rank $r$ rep­re­sent mix­tures of $r$ inde­pen­dent dis­tri­b­u­tions for two ran­dom vari­ables. Like­li­hood infer­ence for this model leads to prob­lems in real alge­braic geom­e­try that we address in this paper. We char­ac­ter­ize the set of fixed points of Expec­ta­tion Max­i­miza­tion, and we study the bound­ary of the space of matri­ces with non­neg­a­tive rank at most $3$. Both of these cor­re­spond to alge­braic vari­eties with many irre­ducible components.

Michael Joswig; Long and Winding Central Paths

May 23, 2014, 3:30pm
LOW 112
Michael Joswig, Insti­tute of Math­e­mat­ics, TU Berlin.
Long and Wind­ing Cen­tral Paths

Abstract: We dis­prove a con­tin­u­ous ana­log of the Hirsch con­jec­ture pro­posed by Deza, Ter­laky and Zinchenko, by con­struct­ing a fam­ily of lin­ear pro­grams with $3r+4$ inequal­i­ties in dimen­sion $2r+2$ where the cen­tral path has a total cur­va­ture in $\Omega(2^r/r)$. Our method is to trop­i­cal­ize the cen­tral path in lin­ear pro­gram­ming. The trop­i­cal cen­tral path is the piecewise-linear limit of the cen­tral paths of para­me­ter­ized fam­i­lies of clas­si­cal lin­ear pro­grams viewed through log­a­rith­mic glasses. We show in par­tic­u­lar that the trop­i­cal ana­logue of the ana­lytic cen­ter is noth­ing but the trop­i­cal barycen­ter, that is, the max­i­mum of a trop­i­cal poly­he­dron. It fol­lows that unlike in the clas­si­cal case, the trop­i­cal cen­tral path may lie on the bound­ary of the trop­i­cal­iza­tion of the fea­si­ble set, and may even coin­cide with a path of the trop­i­cal sim­plex method. Finally, our counter-example is obtained as a defor­ma­tion of a fam­ily of trop­i­cal lin­ear pro­grams intro­duced by Bezem, Nieuwen­huis and Rodr\‘iguez-Carbonell.

This is joint work with Xavier Allami­geon, Pas­cal Benchi­mol and St\‘ephane Gaubert.

Noah Simon; Flexible Sparse Modeling

May 13, 2014, 4:00pm
EEB 303
Noah Simon, Depart­ment of Bio­sta­tis­tics, Uni­ver­sity of Wash­ing­ton.
Flex­i­ble Sparse Modeling

Abstract: Our abil­ity to col­lect data has exploded over recent years. Across sci­ence and busi­ness, we now col­lect thou­sands to mil­lions of mea­sure­ments on each per­son. It is often of inter­est to use these mea­sure­ments to pre­dict some response (eg. like­li­hood of get­ting a dis­ease, or prob­a­bil­ity of click­ing a link). Meth­ods for this prob­lem must bal­ance 3 objec­tives: they must be pre­dic­tive, they must be com­pu­ta­tion­ally tractable, and, in many appli­ca­tions, they must be inter­pretable. Many machine learn­ing meth­ods are highly suc­cess­ful at the first two, but are black boxes. In con­trast, the Lasso (l1 penal­ized regres­sion) is inter­pretable and com­pu­ta­tion­ally tractable, but assumes lin­ear­ity which lim­its its pre­dic­tive accuracy.

In this talk we will dis­cuss a class of sparse addi­tive mod­els induced by com­bin­ing spar­sity and struc­tural penal­ties. These are more flex­i­ble than the stan­dard lin­ear penal­ized model, but main­tain its inter­pretabil­ity and com­pu­ta­tional tractabil­ity. We will show when these penal­ties can and can­not be com­bined to induce the desired struc­ture and spar­sity. We will give an effi­cient algo­rithm for fit­ting a wide class of these mod­els. And we will show that some of these mod­els have desir­able the­o­ret­i­cal properties.

This is joint work with Ash­ley Petersen and Daniela Wit­ten (UW).