Recovering a quadratic form from a finite set of values Say I want to recover the matrix of a positive quadratic form from its values on a finite collection of points. That is, given vectors $x_i \in \mathbb{R}^n$ and the values $x_i^TAx_i$, I want to find the positive semidefinite matrix $A$. I know this can be written as a semidefinite program, but is there a more clever way that exposes more of the structure of the problem, or conditions for when it can and can't be done?
Edit: For clarity, I am not giving myself freedom to choose the $x_i$; I want to address the problem with arbitrarily sampled points.
 A: Let $x_i = \begin{pmatrix}x_i^1 \\ \vdots \\ x_i^n \end{pmatrix}$ for $1\leq i \leq m$ and $(A)_{ij} = a^{ij}$. The quadratic form $q(x_i) = x_iA^Tx_i = \sum\limits_{j=1}^n a^{jj}(x_i^j)^2 + \sum\limits_{k=1 \\ k < j}^n \sum\limits_{j=1}^n (2a^{jk})x_i^jx_i^k$. This is a summation of $\frac{n(n+1)}{2}$ terms. Define an index $1\leq \ell\leq \frac{n(n+1)}{2}$ for the terms in the sum, and let $b^\ell$ be the coefficients and $y_i^\ell$ be the $x_i$-products. Define the matrix $(Y)_{i\ell} = y_i^\ell$ and the vectors $(B)_\ell = b^\ell$ and $(Q)_i = q(x_i)$, so that the equation $YB=Q$ represents the $m$ simultaneous linear equations for the $\frac{n(n+1)}{2}$ coefficients of the quadratic form.
Using this framework, we can see the condition for determining $A$:
If $m\geq\frac{n(n+1)}{2}$ and there exists a matrix $Y'$ constructed from $\frac{n(n+1)}{2}$ distinct rows of $Y$ such that $\det Y' \neq 0$, then $B = (Y')^{-1}Q'$, where $Q'$ is the vector constructed from those same rows of $Q$. Then, $A$ can be determined from $B$.
