Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Functional connectomes (FCs) containing pairwise estimations of functional couplings between pairs of brain regions are commonly represented by correlation matrices. As symmetric positive definite matrices, FCs can be transformed via tangent space projecti ...

Unsupervised Domain Adaptation Regression (DAR) aims to bridge the domain gap between a labeled source dataset and an unlabelled target dataset for regression problems. Recent works mostly focus on learning a deep feature encoder by minimizing the discrepa ...

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

This paper is concerned with two improved variants of the Hutch++ algorithm for estimating the trace of a square matrix, implicitly given through matrix-vector products. Hutch++ combines randomized low-rank approximation in a first phase with stochastic tr ...

We consider the problem of finding a saddle point for the convex-concave objective

\min_x \max_y f(x) + \langle Ax, y\rangle - g^*(y)

, where

f

is a convex function with locally Lipschitz gradient and

g

is convex and possibly non-smooth. We propose an ...

In many problems such as phase retrieval, molecular biology, source localization, and sensor array calibration, one can measure vector differences between pairs of points and attempt to recover the position of these points; this class of problems is called ...

The problem of finding a k x k submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix can a ...

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct algorithm for solving large SDP problems by economizing on both the storage an ...

Many techniques for data science and uncertainty quantification demand efficient tools to handle Gaussian random fields, which are defined in terms of their mean functions and covariance operators. Recently, parameterized Gaussian random fields have gained ...

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...

Several important applications, such as streaming PCA and semidefinite programming, involve a large-scale positive-semidefinite (psd) matrix that is presented as a sequence of linear updates. Because of storage limitations, it may only be possible to retai ...

We analyze the accuracy of the discrete least-squares approximation of a function

u

in multivariate polynomial spaces

P_\Lambda:=span\{y\mapsto y^\nu \,: \, \nu\in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma:=[-1,1]^d

, based on the s ...

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditio ...

Given any twisting cochain t:C→A , where C is a connected, coaugmented chain coalgebra and A is an augmented chain algebra over an arbitrary commutative ring R, we construct a twisted extension of chain complexes Full-size image (1 K) of which both the wel ...

Let X be a finite set and let k be a commutative ring. We consider the k-algebra of the monoid of all relations on X, modulo the ideal generated by the relations factorizing through a set of cardinality strictly smaller than Card(X), called inessential rel ...

Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that ...

In this paper, we study the problem of approximately computing the product of two real matrices. In particular, we analyze a dimensionality-reduction-based approximation algorithm due to Sarlos [1], introducing the notion of nuclear rank as the ratio of th ...

This thesis is concerned with the algebraic theory of hermitian forms. It is organized in two parts. The first, consisting of the first two chapters, deals with some descent properties of unimodular hermitian forms over central simple algebras with involut ...

Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials

Chat with Graph Search

Tangent functional connectomes uncover more unique phenotypic traits

DARE-GRAM : Unsupervised Domain Adaptation Regression by Aligning Inverse Gram Matrices

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

IMPROVED VARIANTS OF THE HUTCH plus plus ALGORITHM FOR TRACE ESTIMATION

A first-order primal-dual method with adaptivity to local smoothness

Coordinate Difference Matrices

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Scalable Semidefinite Programming

Certified And Fast Computations With Shallow Covariance Kernels

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data

Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

A block algorithm for computing antitriangular factorizations of symmetric matrices

The Hochschild complex of a twisting cochain

The algebra of essential relations on a finite set

Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs

Approximate Matrix Multiplication with Application to Linear Embeddings

Hermitian Forms over Algebras with Involution and Hermitian Categories