Applied Algebra Seminar Spring 2021: Difference between revisions

From UW-Math Wiki
Jump to navigation Jump to search
No edit summary
(12 intermediate revisions by 2 users not shown)
Line 2: Line 2:


'''Where''':  Virtual: [https://uwmadison.zoom.us/j/93664753217 https://uwmadison.zoom.us/j/93664753217]
'''Where''':  Virtual: [https://uwmadison.zoom.us/j/93664753217 https://uwmadison.zoom.us/j/93664753217]
 
'''List''':  mathaas@lists.wisc.edu, to join email join-mathaas@lists.wisc.edu
'''List''':  to join email mathaas+join@g-groups.wisc.edu and subscribe to the google group


'''Contact''':  Shamgar Gurevich, Jose Israel Rodriguez, [https://sites.google.com/view/julialindberg/home/ Julia Lindberg] (Lead)
'''Contact''':  Shamgar Gurevich, Jose Israel Rodriguez, [https://sites.google.com/view/julialindberg/home/ Julia Lindberg] (Lead)
Line 21: Line 21:
|February 25
|February 25
| [https://sites.google.com/site/grrigg/ Greg Blekherman (Georgia Tech)]
| [https://sites.google.com/site/grrigg/ Greg Blekherman (Georgia Tech)]
| TBD
| [[#Greg Blekherman|Locally Positive Semidefinite Matrices]]
| Virtual
| Virtual
|-
|-
Line 29: Line 29:
| Virtual
| Virtual
|-
|-
|April 22
|April 22 (At the new 11am time!)
|TBD
| [https://www.damtp.cam.ac.uk/user/hf323/ Hamza Fawzi (Cambridge)]
|  
| TBD
| Virtual
|-
|May 13 (At the new 11am time!)
| [https://people.maths.ox.ac.uk/seigal/ Anna Seigal (University of Oxford)]
|Invariant Theory for Maximum Likelihood Estimation
| Virtual
|-
|-
   
   
Line 66: Line 72:


== Abstracts ==
== Abstracts ==
===Greg Blekherman===
'''Locally Positive Semidefinite Matrices
'''
The cone of positive semidefinite matrices plays a prominent role in optimization, and many hard computational problems have well-performing semidefinite relaxations. In practice, enforcing the constraint that a large matrix is positive semidefinite can be expensive. We introduce the cone of k-locally posiitive semidefinite matrices, which consists of matrices all of whose k by k principal submatrices are positive semidefinite. We consider the distance between the cones of positive and locally positive semidefinite matrices, and possible eigenvalues of locally positive semidefinite matrices. Hyperbolic polynomials play a role in some of the proofs. Joint work with Santanu Dey, Marco Molinaro, Kevin Shu and Shengding Sun.
----
===Carla Michini===
===Carla Michini===
'''Short simplex paths in lattice polytopes
'''Short simplex paths in lattice polytopes
Line 97: Line 111:
| Several talks on tensors  
| Several talks on tensors  
|-
|-
|2nd Thursday of the month
|1:30pm, 2nd Thursday of the month
|[https://www.math.wisc.edu/wiki/index.php/Algebra_in_Statistics_and_Computation_Seminar Informal Seminar: Algebra in Statistics and Computation]
|[https://www.math.wisc.edu/wiki/index.php/Algebra_in_Statistics_and_Computation_Seminar Informal Seminar: Algebra in Statistics and Computation]
|Virtual
|Virtual
Line 105: Line 119:
|Virtual
|Virtual
|-
|-
|2nd Tuesday of the month, 10am
|10am, 2nd Tuesday of the month
|[http://wiki.siam.org/siag-ag/index.php/Webinar SIAM SAGA]   
|[http://wiki.siam.org/siag-ag/index.php/Webinar SIAM SAGA]   
|Virtual: [https://www.youtube.com/playlist?list=PLf_ipOSbWC84HloBwtq3vVJKYE4rwfeSs Recordings]
|Virtual: [https://www.youtube.com/playlist?list=PLf_ipOSbWC84HloBwtq3vVJKYE4rwfeSs Recordings]
|[https://siam.zoom.us/webinar/register/WN_nMdM3GXHTTuZyjn5fGf4jA Registration] needed once.
|[https://siam.zoom.us/webinar/register/WN_nMdM3GXHTTuZyjn5fGf4jA Registration] needed once.
|-
|-
|Most Tuesdays, 10am
|10am, Most Tuesdays
|[https://www.mis.mpg.de/nlalg/seminars/naso.html Nonlinear algebra seminar online]   
|[https://www.mis.mpg.de/nlalg/seminars/naso.html Nonlinear algebra seminar online]   
|Virtual: [https://www.mis.mpg.de/nlalg/seminars/2020.html#id31516 Recordings]
|Virtual: [https://www.mis.mpg.de/nlalg/seminars/2020.html#id31516 Recordings]

Revision as of 15:49, 4 March 2021

When: 1:30pm, Thursdays

Where: Virtual: https://uwmadison.zoom.us/j/93664753217

List: to join email mathaas+join@g-groups.wisc.edu and subscribe to the google group

Contact: Shamgar Gurevich, Jose Israel Rodriguez, Julia Lindberg (Lead)

Remark: This seminar is held on the fourth Thursday of the month


Spring 2021 Schedule

date speaker title host(s)
February 25 Greg Blekherman (Georgia Tech) Locally Positive Semidefinite Matrices Virtual
March 25 James Saunderson (Monash University) TBD Virtual
April 22 (At the new 11am time!) Hamza Fawzi (Cambridge) TBD Virtual
May 13 (At the new 11am time!) Anna Seigal (University of Oxford) Invariant Theory for Maximum Likelihood Estimation Virtual

Spring 2020 Schedule

date speaker title host(s)
February 20 Carla Michini (UW Madison) Short simplex paths in lattice polytopes Local
March 5 Alisha Zachariah (UW Madison) Efficient Estimation of a Sparse Delay-Doopler Channel Local
March 19 Spring Break
March 26 (Seminar on Hiatus because of Covid-19)

Abstracts

Greg Blekherman

Locally Positive Semidefinite Matrices

The cone of positive semidefinite matrices plays a prominent role in optimization, and many hard computational problems have well-performing semidefinite relaxations. In practice, enforcing the constraint that a large matrix is positive semidefinite can be expensive. We introduce the cone of k-locally posiitive semidefinite matrices, which consists of matrices all of whose k by k principal submatrices are positive semidefinite. We consider the distance between the cones of positive and locally positive semidefinite matrices, and possible eigenvalues of locally positive semidefinite matrices. Hyperbolic polynomials play a role in some of the proofs. Joint work with Santanu Dey, Marco Molinaro, Kevin Shu and Shengding Sun.


Carla Michini

Short simplex paths in lattice polytopes

We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time. This is a joint work with Alberto Del Pia.


Alisha Zachariah

Efficiently Estimating a Sparse Delay-Doppler Channel

Multiple wireless sensing tasks, e.g., radar detection for driver safety, involve estimating the ”channel” or relationship between signal transmitted and received. In this talk, I will focus on a certain type of channel known as the delay-doppler channel. This channel model starts to be applicable in high frequency carrier settings, which are increasingly common with recent developments in mmWave technology. Moreover, in this setting, both the channel model and existing technologies are amenable to working with signals of large bandwidth, and using such signals is a standard approach to achieving high resolution channel estimation. However, when high resolution is desirable, this approach creates a tension with the desire for efficiency because, in particular, it immediately implies that the signals in play live in a space of very high dimension N (e.g., ~10^6 in some applications), as per the Shannon-Nyquist sampling theorem.

To address this, I will propose a randomized algorithm for channel estimation in the k-sparse setting (e.g., k objects in radar detection), with sampling and space complexity both on the order of k(log N)^2, and arithmetic complexity on the order of k(log N)^3+k^2, for N sufficiently large.

While this algorithm seems to be extremely efficient -- to the best of our knowledge, the first of this nature in terms of complexity -- it is just a simple combination of three ingredients, two of which are well-known and widely used, namely digital chirp signals and discrete Gaussian filter functions, and the third being recent developments in Sparse Fast Fourier Transform algorithms.


Related events to note

date event/title location/speaker info
Postponed Applied Algebra Days 4 - Tensors Several talks on tensors
1:30pm, 2nd Thursday of the month Informal Seminar: Algebra in Statistics and Computation Virtual
3:30pm SIAM Student Chapter Virtual
10am, 2nd Tuesday of the month SIAM SAGA Virtual: Recordings Registration needed once.
10am, Most Tuesdays Nonlinear algebra seminar online Virtual: Recordings Registration required once
Biweekly Mondays Algebraic Statistics Online Seminar (ASOS) Virtual: Recordings Mailing list sign-up for Zoom-links
January 26th-29th, 2021 Sanya Workshop on Algebraic Geometry and Machine Learning Virtual: Recordings
July 29-30, 2021 Real algebraic geometry and convex geometry Conference TBD: TU Braunschweig, Germany or Online