random cohomology for quantum nerds - 2019-11-15

« first day (529 days earlier) ← previous day next day → last day (1054 days later) »

8:37 PM

I'mma post some optimization rant here

So here's the setup. I have some polyhedron in $\Bbb R^n$, given in "standard form", so all points $\mathbf{x} \in \Bbb R^n$ such that $A\mathbf{x} = \mathbf{b}$ and $\mathbf{x} \geq 0$ for some $m \times n$ matrix $A$. Let's call this polyhedron $P$.

Optimization people forget the geometry and just think of it as a system of equalities/inequalities with sign constrains on the variables. You can prove any such system can be reduced to the standard form as an easy exercise.

If the polyhedron $P$ is nonempty, we call the system feasible, as usual. Note that if it's feasible you can assume WLOG that $A$ is full row rank $\rho(A) = m$, because suppose the rows of $A$ as $\mathbf{a}_i$, then the system of equality constraints are $\mathbf{a}_i^\sf{T} \mathbf{x} = b_i$. If some $\mathbf{a}_j$ is a linear combination of other $\mathbf{a}_i$'s, then the corresponding statement must be true about $b_j$ being a linear combination of $b_i$'s as well by feasibility.

So you can just throw the whole constraint out as redundant.

The geometry is that $A\mathbf{x} = \mathbf{b}$ is some affine hyperplane in $\Bbb R^n$ (plane of the polyhedron) and $\mathbf{x} \geq 0$ cuts out $P$ inside that plane. Think $x_1 + x_2 + x_3 = 1$ and $x_i \geq 0$ for $i = 1, 2, 3$. That's a triangle inside the 2D plane of the polyhedron.

The first leap is to understand the vertices of $P$ completely algebraically. This is trivial but groundbreaking: Call a constraint in the system $P = \{\mathbf{a}_i^\sf{T} \mathbf{x} = b_i, x_j \geq 0\}$ "active" at some point $\mathbf{x}^* \in P$ if that constraint is an equality at $\mathbf{x}^*$.

For example in the example I gave, the constraint $x_1 \geq 0$ is active at $(0, 1/2, 1/2)$.

A point $\mathbf{x}^* \in \Bbb R^n$ is a vertex of $P$ if it's a feasible solution, i.e, $\mathbf{x}^* \in P$, and there are $n$ linearly independent constraints which are active at $\mathbf{x}^*$.

Think $(1, 0, 0)$ in the example I gave. $x_1 + x_2 + x_3 = 1$, $x_2 \geq 0$ and $x_3 \geq 0$ are the $3$ linearly independent active constraints at this point.

8:54 PM

Balarka Sen has added Semiclassical to the list of this room's owners.

Hi!

Leaky Nun has removed Semiclassical from the list of this room's owners.

Alessandro Codenotti

Uh I remember I once tried to learn some of that stuff, but I ran away quickly

@LeakyNun Uh, why?

Alessandro Codenotti

That's harsh @Leaky

8:54 PM

oops

Hi. Having fun with polyhedra and optimization I see

Leaky Nun has added Semiclassical to the list of this room's owners.

Yup, @Semiclassical

For the mammoth paper I contributed to I had to learn some of that stuff

It's damn cool, it's amazing how technical yet powerful it can be

8:56 PM

yeah

The context for me was Bell’s inequality in QM

In the beginning of the course I was pretty disappointed by it; it felt like engineering. But I was wrong; this algorithmic point of view is absolutely worth learning

The whole point I think is how CS people think about the whole thing. The geometry of it all is not nontrivial, it's just the way they formulate it

Which ends up meaning “these three numbers lie in a tetrahedron”, with bells inequality just being one of the facets of the tetrahedron

Aha

(Well, one of the inequalities. But you can get the other three just by flipping some things)

If you try to generalize this from spin-1/2 to higher spin analogues, you get more and more complicated polyhedra the larger you make the spin

Complicated both in terms of “many vertices/edges” but also higher and higher dimensional

To make it visualizable, I had a projection back down to 3D

Let me find the link so you can see the pics

I'll continue with the rant, please keep talking over me if you feel like it: The vertex idea is basically the following; since our polyhedra are in standard form, the equality constraints $A\mathbf{x} = \mathbf{b}$ have to be satisfied because of feasibility. This already constitutes to $m$ linearly independent active constraints. So we have to get $n-m$ more active linearly independent constraints, which we get from choosing from the sign constraints $\mathbf{x} \geq 0$

9:02 PM

Ok, pages 103, 107, 117 here: arxiv.org/abs/1910.10688

The idea is that it's a polyhedron in $\mathbf{R}^{n-m}$ (Ax = b being plane of the polyhedron, which is codimension m), basically, so at a vertex the number of faces adjacent should be at least uh $n - m$ (think the vertex of a standard $(n-m)$-simplex).

Had to learn a bit about the linear programming connection to write my portion of that

Every sign constraint gives a face of the polyhedron

Tarski–Seidenberg theorem

In mathematics, the Tarski–Seidenberg theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities. The theorem—also known as the Tarski–Seidenberg projection property—is named after Alfred Tarski and Abraham Seidenberg. It implies that quantifier elimination is possible over the reals, that is that every formula constructed from polynomial equations and inequalities by logical connectors ∨ (or), ∧ (and), ¬ (not)...

Huzzah for the H-representation

9:04 PM

Yeah that's a great theorem

A baby version of this is that projection of a polyhedron is a polyhedron, which is useful in Fourier-Motzkin algorithm

Actually, one thing that was a big computational hurdle for me was how hard it is to convert from an H-representation to a V-representation

Cool pictures, @SemiC

Which it seemed like we always needed at first: getting the H-rep was easy enough for us, but to project down to 3D we seemed to need the V-rep

Luckily there’s a nice convex-hull algorithm that lets you get the projection from the H-rep directly

Notably, the original paper on that algorithm explicitly draws the connection to quantifier elimination: semanticscholar.org/paper/…

These notes were pretty handy in general: faculty.coe.drexel.edu/jwalsh/JayantCHM.pdf

I don't know too many projection algorithms. I know Fourier-Motzkin gets exponentially harder with the number of constraints

Right.

9:11 PM

@LeakyNun What's the relation with quantifier elimination, by the way? Is it easy to see

See page 84 of the notes I linked for the algorithm

Thanks, I will check it out

@BalarkaSen the image is basically an existential

the image of xy-1 in R is $\{y \mid \color{red}{\exists x}, xy-1=0\}$

@LeakyNun Hm, something like, $x \in \Pi(S)$ basically means $\exists y \in S$ such that $\pi(y) = x$?

exactly

eliminating the existential means that the resulting set is semi-algebraic

9:13 PM

Interesting point of view

I love it!

ncatlab.org/nlab/show/Tarski-Seidenberg+theorem

I’ll note also that the polytopes stuff was entirely on the classical side of our paper

On the quantum side, what you get is not linear programming but semidefinite programming

I have heard the name "o-minimal structures" flying around

What's semidefinite programming, in summary @Semiclassical?

You replace linear inequalities with semidefiniteness constraints

So, for instance, you might demand that x,y,z be such that the matrix {{1,x,y},{x,1,z},{y,z,1}} be positive-semidefinite

And then minimize a quantity like x+y+z over that set

The main new thing is that the feasibility region is now semi algebraic rather than polyhedral

Ah gotcha

9:21 PM

I should emphasize that the connection to semidefinite programming is a bit complicated in QM. For the simple problem we were considering, you only need to consider one SD program. In general, though, one needs consider a possibly infinite sequence of such SDPs

Which is altogether less nice

The basic problem is this: if someone gives you the supposed behavior of a quantum system, can you certify (1( whether you could actually get that behavior in QM, and (2) could you produce that same behavior with a classical model

That’s not so hard to do if you assume that the underlying system is, in a certain sense, unbiased

The moment you allow for bias, though, it gets much much harder

Continuing with rant above: The problem of optimization is given some polyhedron $P$, let's say in standard form because why not, minimize some linear function $\mathbf{c}^T \mathbf{x}$ over it. The well-known algorithm for this is the simplex method, which based on the following idea: if a finite optimum is achieved, it's achieved at one of the vertices

This requires a proof but let's trust this for now. The idea is if it's not a vertex then the polyhedron contains some line (NOT ray) passing through that point and you can go towards one direction of the line, and do better. This can be made into a purely algorithmic way to achieve an optimum vertex.

The simplex method then starts at some vertex, and walks along "edges" of the polyhedron, to get to the optimal vertex.

This requires some setup to say purely algebraically. Here's a theorem: if $\mathbf{x}$ is a vertex of $P = \{A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0\}$, then there exists an $m \times m$ nonsingular submatrix $B$ of $A$ obtained from choosing out some indices $B(1), \cdots, B(m)$, called the basic indices, and looking at the corresponding columns $B = [A_{B(1)}, \cdots, A_{B(m)}]$, such that $x_i = 0$ whenever $i \notin \{B(1), \cdots, B(m)\}$

$B$ is called the basis matrix of $\mathbf{x}$ (there may be multiple basis matrices for one vertex) and $x_{B(i)}$ the basic variables

This is a very geometrically unclear idea to me, to be honest. Being a vertex is a natural condition on the rows of $A$, not columns. The picture is as follows; consider the previous example with the triangle on the plane $x_1 + x_2 + x_3 = 1$, with $x_1 = 0$, $x_2 = 0$ and $x_3 = 0$ corresponding to the edges of the triangle. Take $x^* = (1, 0, 0)$ as a vertex. Then $x_1$ is a basic variable

This is the variable corresponding to the edge which is not active at $x^*$

Two vertices $x^*, y^*$ are adjacent in $P$ if they each have some basis which have all but one index in common

I mean, I guess alternatively you can say they are adjacent if there are $n-1$ linearly independent constraints active at either

« first day (529 days earlier) ← previous day next day → last day (1054 days later) »

Transcript for

Nov '1915

♦ $Mathematics$ random cohomology for quantum nerds

covariance is unacceptable

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

$Mathematics$

site design / logo © 2024 Stack Exchange Inc; legal

mobile