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.$$

  • $\begingroup$ The question is w.r.t. a fixed value of m? $\endgroup$ – Mark L. Stone Apr 29 '18 at 18:08
  • $\begingroup$ Yes, fixed -- otherwise I can make $E||x-\hat x||^2$ arbitrarily small. I'll update. $\endgroup$ – Aryeh Kontorovich Apr 29 '18 at 18:37
  • $\begingroup$ 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.) $\endgroup$ – Lutz Mattner Apr 30 '18 at 9:57
  • $\begingroup$ Yes, I've added a further clarification. $\endgroup$ – Aryeh Kontorovich Apr 30 '18 at 10:29
  • 1
    $\begingroup$ This sounds a little bit like "optimal experimental design". $\endgroup$ – 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").

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.