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 13 (Thurs­day — EEB 003)
Henry Wolkow­icz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.
Tak­ing Advan­tage of Degen­er­acy in Cone Opti­miza­tion: with Appli­ca­tions to Sen­sor Net­work Localization

Novem­ber 18
Daniela Wit­ten, Depart­ment of Bio­sta­tis­tics, UW.
Flex­i­ble Graph­i­cal Modeling

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

Decem­ber 2 [COREEEB125]
Peter Bür­gisser, Insti­tute for Math­e­mat­ics, TU Berlin.
Con­di­tion of Con­vex Opti­miza­tion and Spher­i­cal Intrin­sic Volumes

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

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

Click on the title or see below for the abstracts.

Henry Wolkowicz; Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization

Novem­ber 13, 2014, 4:00pm
EEB 003
Henry Wolkow­icz, Depart­ment of Math­e­mat­ics, Uni­ver­sity of Water­loo.
Tak­ing Advan­tage of Degen­er­acy in Cone Opti­miza­tion: with Appli­ca­tions to Sen­sor Net­work Localization

Abstract: The ele­gant the­o­ret­i­cal results for strong dual­ity and strict com­ple­men­tar­ity for lin­ear pro­gram­ming, LP, lie behind the suc­cess of cur­rent algo­rithms. How­ever, the the­ory and pre­pro­cess­ing tech­niques that are suc­cess­ful for LP can fail for cone pro­gram­ming over non­poly­he­dral cones.

Sur­pris­ingly, many impor­tant appli­ca­tions of semi­def­i­nite pro­gram­ming, SDP, that arise from relax­ations of hard com­bi­na­to­r­ial prob­lems are degen­er­ate. (Slater’s con­straint qual­i­fi­ca­tion fails.) This includes relax­ations for prob­lems such as the: Qua­dratic Assign­ment; Graph Par­ti­tion­ing; Set Cov­er­ing and par­ti­tion­ing; and sen­sor net­work local­iza­tion and mol­e­c­u­lar con­for­ma­tion. Rather than being a dis­ad­van­tage, we show that this degen­er­acy can be exploited. In par­tic­u­lar, sev­eral huge instances of SDP com­ple­tion prob­lems can be solved quickly and to extremely high accu­racy. In par­tic­u­lar, we illus­trate this on the sen­sor net­work local­iza­tion problem.

Peter Bürgisser; Condition of Convex Optimization and Spherical Intrinsic Volumes

CORE Series
Decem­ber 2, 2014, 4:00pm
EE 125
Peter Bür­gisser, Insti­tute for Math­e­mat­ics, TU Berlin.
Con­di­tion of Con­vex Opti­miza­tion and Spher­i­cal Intrin­sic Volumes

Abstract: The analy­sis of the sta­bil­ity and effi­ciency of algo­rithms for con­vex opti­miza­tion nat­u­rally leads to the study of con­di­tion num­bers. The Grass­mann con­di­tion, which is a geo­met­ric ver­sion of Renegar’s con­di­tion, is espe­cially suited for a prob­a­bilis­tic analy­sis. Such analy­sis can be per­formed by rely­ing on tech­niques from spher­i­cal con­vex geom­e­try and dif­fer­en­tial geom­e­try. Along this way, we obtain an aver­age analy­sis of the Grass­mann con­di­tion num­ber that holds for any reg­u­lar con­vex cone. A closer look prompts the inves­ti­ga­tion of the spher­i­cal coun­ter­parts of intrin­sic vol­umes — a notion thor­oughly stud­ied for euclid­ean spaces, but much less so for spheres, so that many fas­ci­nat­ing ques­tions remain.
Joint work with Den­nis Amelunxen.

Peter Bürgisser

Bio: Peter Bür­gisser has been a pro­fes­sor of Math­e­mat­ics at the Tech­ni­cal Uni­ver­sity of Berlin since 2013. Prior to that he was a pro­fes­sor of Math­e­mat­ics at the Uni­ver­sity of Pader­born. His research inter­ests are alge­braic com­plex­ity the­ory, sym­bolic and numeric com­pu­ta­tion, and more recently, the prob­a­bilis­tic analy­sis of numer­i­cal algo­rithms. Bür­gisser was an invited speaker at the Inter­na­tional Con­gress of Math­e­mati­cians in Hyder­abad in 2010 and ple­nary speaker at Foun­da­tions of Com­pu­ta­tional Math­e­mat­ics 2008 in Hong Kong. He is an asso­ciate edi­tor of Com­pu­ta­tional Com­plex­ity, and an edi­tor of the jour­nal Foun­da­tions of Com­pu­ta­tional Math­e­mat­ics. He served as a work­shop co-organizer for the Foun­da­tions of Com­pu­ta­tional Math­e­mat­ics con­fer­ences (2005, 2008, 2011), for the Spe­cial Year on Appli­ca­tions of Alge­braic Geom­e­try (IMA 2006/2007), and for the Ober­wol­fach work­shops on Com­plex­ity The­ory (2009, 2012). His research inter­ests lie in alge­braic com­plex­ity the­ory: both the design of effi­cient algo­rithms for alge­braic prob­lems, and the quest for lower bounds.

Daniela Witten; Flexible Graphical Modeling

Novem­ber 18, 2014, 4:00pm
GUG 204
Daniela Wit­ten, Depart­ments of Bio­sta­tis­tics and Sta­tis­tics, UW.
Flex­i­ble Graph­i­cal Modeling

Abstract: In recent years, there has been con­sid­er­able inter­est in esti­mat­ing con­di­tional depen­dence rela­tion­ships among ran­dom vari­ables in the high-dimensional set­ting, in which the num­ber of vari­ables far exceeds the num­ber of avail­able obser­va­tions. Most prior work has assumed that the vari­ables are mul­ti­vari­ate Gauss­ian, or that the con­di­tional means of the vari­ables are lin­ear. Unfor­tu­nately, if these assump­tions are vio­lated, then the result­ing esti­mates can be inaccurate.

I will present two recent lines of work on learn­ing the con­di­tional depen­dence graph of a set of ran­dom vari­ables in the non-Gaussian set­ting. First, I will present a semi-parametric method that allows the con­di­tional means of the fea­tures to take on an arbi­trary addi­tive form. Next, I will present an approach for learn­ing a graph in which the dis­tri­b­u­tion of each node, con­di­tioned on the oth­ers, may have a dif­fer­ent para­met­ric form. Each approach is for­mu­lated as the solu­tion to a con­vex opti­miza­tion prob­lem cor­re­spond­ing to a penal­ized log likelihood.

This is joint work with Ali Sho­jaie, Shizhe Chen, and Arend Voorman.

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.