Skip to main content
MathOverflow

Return to Question

added 133 characters in body
Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

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, https://mathoverflow.net/questions/297755/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.$$

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, https://mathoverflow.net/questions/297755/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.

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, https://mathoverflow.net/questions/297755/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.$$

added 26 characters in body
Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

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, https://mathoverflow.net/questions/297755/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.

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, https://mathoverflow.net/questions/297755/can-i-really-double-my-accuracy-on-variance-of-a-sum-of-random-variables which is a (very) simple special case of the above.

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, https://mathoverflow.net/questions/297755/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.

Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

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, https://mathoverflow.net/questions/297755/can-i-really-double-my-accuracy-on-variance-of-a-sum-of-random-variables which is a (very) simple special case of the above.