Events

Location:  MC 5479

There will be a social starting at 1:00 pm.

This seminar will consist of 3 short talks by undergraduate students. There will be a coffee break at 1:30 pm.

Title: Nonnegative Matrix Factorization in non-standard settings, for fun

Abstract: This abstract is broken into 6 points.

1. What is NMF: NMF is to find two elementwise nonnegative low-rank matrices W and H such that M ≈ WH for a given elementwise nonnegative matrix M.

2. NMF is commonly done in the Euclidean distance.

3. I argue that Euclidean distance is "not good", and a ray-to-ray distance is better.

4. Under L2-normalization onto the unit sphere, we arrive at the cosine angle distance, which motivates the use of manifold optimization techniques.

5. Under L1-normalization onto the simplex, we arrive at the so-called Aitchison geometry, which contains funny algebra.

6. Why do these: for curiosity and fun. For application, these non-standard NMF can "remove cloud" from satellite images.

Title: Quartic quantum speedups for planted inference

Abstract: Consider the following task ("noisy 4XOR"), arising in CSPs, optimization, and cryptography.  There is a 'secret' Boolean vector x in {-1,+1}^n.  One gets m randomly chosen pairs (S, b), where S is a set of 4 coordinates from [n] and b is x^S := prod_{i in S} x_i with probability 1-eps, and -x^S with probability eps.  Can you tell the difference between the cases eps = 0.1 and eps = 0.5? 

Title: Oddities in the pursuit of self-duality

Abstract: Certain important cones in conic optimization are self-dual, e.g., the positive semidefinite matrices and the nonnegative orthant. In this talk we will address the problem of determining which convex cones are self-dual in a broad sense, which allows changing the underlying inner product if necessary. We will describe some recent progress on this question for polyhedral cones and discuss some unexpected connections. In particular, we will show a curious result connecting self-dual polyhedral cones and extreme rays of doubly nonnegative matrices. We will also discuss how semidefinite programming can be used to search for self-dual polyhedral cones. Time allowing, we will describe new results on the related problem of determining the automorphisms of certain cones of interest.

This talk is based on joint works with João Gouveia and Masaru Ito.