Publications related to Matrix Completion on Graphs

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Statistical limits of dictionary learning: Random matrix theory and the spectral replica method

Nicolas Macris, Jean François Emmanuel Barbier

We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, in the challenging regime where the matrices to infer have a rank growing linearly with the system size. This is in contrast with most existin ...

AMER PHYSICAL SOC2022

A Determinantal Identity for the Permanent of a Rank 2 Matrix

Adam Wade Marcus

We prove an identity relating the permanent of a rank 2 matrix and the determinants of its Hadamard powers. When viewed in the right way, the resulting formula looks strikingly similar to an identity of Carlitz and Levine, suggesting the possibility that t ...

TAYLOR & FRANCIS INC2022

The Dimension of the Body in Higher Education: Matrix of Meanings in Students’ Diaries

Simon Nessim Henein, Ramiro Tau

In this paper, we attempt to show some consequences of bringing the body back into higher education, through the use of performing arts in the curricular context of scientific programs. We start by arguing that dominant traditions in higher education repro ...

2021

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

,

b \in \Z^m

,

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

EPFL2020

Bootstrapping massive quantum field theories

Denis Karateev

We propose a new non-perturbative method for studying UV complete unitary quantum field theories (QFTs) with a mass gap in general number of spacetime dimensions. The method relies on unitarity formulated as positive semi-definiteness of the matrix of inne ...

SPRINGER2020

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Unlabeled Sensing with Random Linear Measurements

Martin Vetterli, Jayakrishnan Unnikrishnan, Saeid Haghighatshoar

We study the problem of solving a linear sensing system when the observations are unlabeled. Specifically we seek a solution to a linear system of equations y = Ax when the order of the observations in the vector y is unknown. Focusing on the setting in wh ...

Institute of Electrical and Electronics Engineers2018

Practical Sketching Algorithms For Low-Rank Matrix Approximation

Volkan Cevher, Alp Yurtsever

This paper describes a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image, or sketch, of the matrix. These methods can preserve structural properties of the input matrix, such as positive-semidefinite ...

Society for Industrial and Applied Mathematics2017

Fast recovery and approximation of hidden Cauchy structure

Robert Gerhard Jérôme Luce

We derive an algorithm of optimal complexity which determines whether a given matrix is a Cauchy matrix, and which exactly recovers the Cauchy points defining a Cauchy matrix from the matrix entries. Moreover, we study how to approximate a given matrix by ...

Elsevier Science Inc2016

Matrix Completion on Graphs

Graph Chatbot

Chat with Graph Search

The double exponential runtime is tight for 2-stage stochastic ILPs

Statistical limits of dictionary learning: Random matrix theory and the spectral replica method

A Determinantal Identity for the Permanent of a Rank 2 Matrix

The Dimension of the Body in Higher Education: Matrix of Meanings in Students’ Diaries

New Results in Integer and Lattice Programming

Bootstrapping massive quantum field theories

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Unlabeled Sensing with Random Linear Measurements

Practical Sketching Algorithms For Low-Rank Matrix Approximation

Fast recovery and approximation of hidden Cauchy structure

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Bootstrapping massive quantum field theories

New Results in Integer and Lattice Programming

A Determinantal Identity for the Permanent of a Rank 2 Matrix

Statistical limits of dictionary learning: Random matrix theory and the spectral replica method

The Dimension of the Body in Higher Education: Matrix of Meanings in Students’ Diaries

The double exponential runtime is tight for 2-stage stochastic ILPs

Unlabeled Sensing with Random Linear Measurements

Fast recovery and approximation of hidden Cauchy structure

Practical Sketching Algorithms For Low-Rank Matrix Approximation