# Difference between revisions of "Applied Algebra Seminar Spring 2020"

(44 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

+ | '''When''': 11:00am, Thursdays | ||

+ | |||

+ | '''Where''': 901 Van Vleck Hall | ||

+ | |||

+ | '''List''': mathaas@lists.wisc.edu, to join email join-mathaas@lists.wisc.edu | ||

+ | |||

+ | '''Contact''': Shamgar Gurevich, Jose Israel Rodriguez | ||

+ | |||

+ | '''Remark''': We usually have a gap of around 2-3 weeks between seminars. | ||

+ | |||

+ | |||

== Spring 2020 Schedule == | == Spring 2020 Schedule == | ||

Line 13: | Line 24: | ||

|- | |- | ||

|February 27 | |February 27 | ||

+ | | | ||

+ | | | ||

+ | |- | ||

+ | |March 5 | ||

+ | | [https://www.math.wisc.edu/~rzachariah/// Alisha Zachariah (UW Madison)] | ||

+ | | [[#Alisha Zachariah|Efficient Estimation of a Sparse Delay-Doopler Channel]] | ||

+ | | Local | ||

+ | |- | ||

+ | |March 12 | ||

+ | | | ||

+ | | | ||

+ | |- | ||

+ | |March 19 | ||

+ | |Spring Break | ||

+ | | | ||

+ | |- | ||

+ | |March 26 | ||

+ | |(Organizer traveling) | ||

+ | | | ||

+ | |- | ||

+ | |April 2 | ||

+ | | | ||

+ | | | ||

+ | |- | ||

+ | |April 9 | ||

+ | | | ||

+ | | | ||

+ | |- | ||

+ | |April 16 | ||

+ | |[https://www.math.tamu.edu/~jml/// JM Landsberg (Texas A&M)] | ||

+ | |[[#JM Landsberg|TBD]] | ||

+ | | Jose | ||

+ | |-| | ||

+ | |April 23 | ||

| | | | ||

| | | | ||

|- | |- | ||

|} | |} | ||

− | |||

− | |||

== Abstracts == | == Abstracts == | ||

Line 27: | Line 70: | ||

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. | 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. | ||

+ | |||

+ | ---- | ||

+ | == Other events to note == | ||

{| cellpadding="8" | {| cellpadding="8" | ||

!align="left" | date | !align="left" | date | ||

Line 38: | Line 93: | ||

|[https://www.math.wisc.edu/wiki/index.php/Colloquia#Joe_Kileel_.28Princeton.29/// Talk: Inverse Problems, Imaging and Tensor Decomposition] | |[https://www.math.wisc.edu/wiki/index.php/Colloquia#Joe_Kileel_.28Princeton.29/// Talk: Inverse Problems, Imaging and Tensor Decomposition] | ||

|Joe Kileel (Princeton) | |Joe Kileel (Princeton) | ||

+ | |- | ||

+ | |February 10 | ||

+ | |[https://www.math.wisc.edu/wiki/index.php/Colloquia#Cynthia_Vinzant_.28NCSU.29/// Talk: Matroids, log-concavity, and expanders ] | ||

+ | |Cynthia Vinzant (NCSU) | ||

+ | |- | ||

+ | |April 17 | ||

+ | |[https://www.math.wisc.edu/wiki/index.php/Applied_Algebra_Days_Tensors /// Applied Algebra Days 4 - Tensors ] | ||

+ | | Several talks on tensors | ||

|- | |- | ||

|} | |} | ||

+ | ---- |

## Latest revision as of 19:06, 4 March 2020

**When**: 11:00am, Thursdays

**Where**: 901 Van Vleck Hall

**List**: mathaas@lists.wisc.edu, to join email join-mathaas@lists.wisc.edu

**Contact**: Shamgar Gurevich, Jose Israel Rodriguez

**Remark**: We usually have a gap of around 2-3 weeks between seminars.

## Contents

## Spring 2020 Schedule

date | speaker | title | host(s) |
---|---|---|---|

February 20 | Carla Michini (UW Madison) | Short simplex paths in lattice polytopes | Local |

February 27 | |||

March 5 | Alisha Zachariah (UW Madison) | Efficient Estimation of a Sparse Delay-Doopler Channel | Local |

March 12 | |||

March 19 | Spring Break | ||

March 26 | (Organizer traveling) | ||

April 2 | |||

April 9 | |||

April 16 | JM Landsberg (Texas A&M) | TBD | Jose |

April 23 |

## Abstracts

### 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.

## Other events to note

date | event/title | speaker |
---|---|---|

February 7 | Talk: Inverse Problems, Imaging and Tensor Decomposition | Joe Kileel (Princeton) |

February 10 | Talk: Matroids, log-concavity, and expanders | Cynthia Vinzant (NCSU) |

April 17 | /// Applied Algebra Days 4 - Tensors | Several talks on tensors |