3
$\begingroup$

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

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

1 Answer 1

Reset to default
1
$\begingroup$

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").

Improve this answer
$\endgroup$
1
  • $\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
    Commented May 1, 2018 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .