# Optimal linear measurement operator

Let $x\in R^n$ be an unknown vector. Suppose I am allowed to choose any $A\in R^{m\times n}$, under the constraint that each row of $A$ has $\ell_2$ norm at most $1$. Then I carry out a "measurement", which means that I get to observe $Ax+\xi$, where $y=\xi\sim N(0,I_m)$ is iid noise. Finally, I am allowed to apply an arbitrary deterministic function $f:R^m\to R^n$ to estimate $x$ via $\hat x = f(y)$. Question: under the specified constraints, which choice of $A$ (and $f$) minimizes $E||x-\hat x||^2_2$? Has this class of problems been studied somewhere? I was inspired by this question, Can I really double my accuracy? On variance of a sum of random variables which is a (very) simple special case of the above.

Edit: $m,n$ are fixed. Edit 2: I want to find $f:R^m\to R^n$ and a linear $A:R^n\to R^m$ so as to minimize $$\sup_{||x||_2\le 1} E||x-f(Ax+\xi)||^2_2.$$

• The question is w.r.t. a fixed value of m? – Mark L. Stone Apr 29 '18 at 18:08
• Yes, fixed -- otherwise I can make $E||x-\hat x||^2$ arbitrarily small. I'll update. – Aryeh Kontorovich Apr 29 '18 at 18:37
• You want to minimise $\sup_{x\in R^n}E\|x-\hat{x}\|_2^2$ , with respect to $A$ and $f$, right? (I understand you have a function-valued minimisation problem, which for me needs some clarification, perhaps different from my guess. Else, $f$ identically to $x$ would trivially solve the problem.) – Lutz Mattner Apr 30 '18 at 9:57
• Yes, I've added a further clarification. – Aryeh Kontorovich Apr 30 '18 at 10:29
• This sounds a little bit like "optimal experimental design". – Dirk May 1 '18 at 15:02

There is the theory of "optimal experimental design" or "optimal design of experiments". The main question there is "if I want to measure a certain quantity, how should do it in an optimal way?"

"Optimal" can mean many different things here, e.g. that some estimator of the quantity has minimal variance (and this is still not precise, as "variance" is a matrix valued quantity in the multivariate case).

One pointer to the literature is the book by Pukelsheim (if I remember correctly, the book is called "Optimal design of experiments").

• Thanks! I Upvoted, but will hold off on accepting to give a chance to others with potentially more complete answers to chime in... – Aryeh Kontorovich May 1 '18 at 16:19