Skip to content

Files

Latest commit

5c650d8 · Jul 15, 2021

History

History
8 lines (8 loc) · 1.24 KB

README.md

File metadata and controls

8 lines (8 loc) · 1.24 KB

group-testing-rl

HDSI Undergraduate Research Scholarship 2021 project

Current Problem Statement

I am on a gameshow, and the host has an unknown x . I am trying to uncover that x . He samples one row $ \vec{w_1}^T=[w_{11}, w_{12}, ..., w_{1n}]$ from the Walsh matrix without replacement and multiplies it with that x to get y 1 , which is now a scalar, since he sampled one row. I try to find all x ~ such that w 1 x ~ = y 1 is satisfied. I must end up with at most ${n}C{k}$ x ~ 's, including one that is actually equal to x . I keep these all in a pool. Then, the host samples another row, forming the matrix: $\hat{W}=\begin{bmatrix} \vec{w_1}^T \ \vec{w_2}^T \end{bmatrix}$ Select the x ~ 's from the set we have that are consistent with W ^ x = y 2 . We should have less than ${n}C{k}$ solutions. However, once the host samples k l o g 2 ( N ) l o g 2 ( K ) rows, we should only have one unique solution, which is the correct x . If we don't, this is an unsuccessful run. Later, develop a deep policy/reinforcement learning network that can cleverly sample rows of the Walsh matrix such that x is uncovered at the optimal time. Note: Solution will not scale well.