Timeline for Recover unknown vectors with dot-product queries
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2019 at 6:12 | comment | added | Josiah Park | As was mentioned, for generic $V$, the problem just boils down to considering each $v_i$ separately. The points in $V$ would need to be structured in order to be able to infer what $V$ is with less 'measurements' $\langle v,v_i \rangle$, $v\in\mathbb{R}^d$. | |
| Jun 1, 2019 at 0:57 | comment | added | Joseph O'Rourke | @StevenLandsburg: I see... Have to think about this. I meant a single query to be $v \cdot v_i$. Because there is freedom to choose different query vectors $v$, it seems conceivable that intelligent choice of query vectors reduces the total number of queries. But perhaps I am wrong, and it all reduces to determining one $v_i$. | |
| Jun 1, 2019 at 0:45 | comment | added | Steven Landsburg | (I interpret a single query to be a choice of an i and a query vector v. If you really meant that a single query is a query vector v, applied to all n unknown vectors, that would answer my question.) | |
| Jun 1, 2019 at 0:43 | comment | added | Steven Landsburg | No, that's not what I meant. Let s(d,n) be the solution to your problem. It appears that s(d,n)=ns(d,1). So why not just ask for the value of s(d,1)? | |
| Jun 1, 2019 at 0:41 | comment | added | Joseph O'Rourke | @StevenLandsburg: Feel free to concentrate on specific $n$ & $d$. I am hoping that considering all as variants of the same general question will clarify. And I wouldn't want to proliferate questions unnecessarily. | |
| Jun 1, 2019 at 0:38 | comment | added | Steven Landsburg | Why is this presented as one problem, as opposed to $n$ completely separate problems? | |
| Jun 1, 2019 at 0:10 | comment | added | Gerhard Paseman | There is the obvious strategy involving nd queries with a known orthonormal frame. Indeed, one needs nd queries in this case unless one finds some components of the mystery vectors are zero: any nonzero unknown could appear with positive or negative sign. Gerhard "Almost Surely ND Are Best" Paseman, 2019.05.31. | |
| May 31, 2019 at 23:27 | history | edited | Joseph O'Rourke | CC BY-SA 4.0 |
added 43 characters in body
|
| May 31, 2019 at 23:19 | history | asked | Joseph O'Rourke | CC BY-SA 4.0 |