Tidal river dynamics: Implications for deltas : TIDAL RIVER DYNAMICS

We consider the problem of reconstructing a sparse signal \(x^0\in\R^n\) from a limited number of linear measurements. Given \(m\) randomly selected samples of \(U x^0\), where \(U\) is an orthonormal matrix, we show that \(\ell_1\) minimization recovers \(x^0\) exactly when the number of measurements exceeds \[ m\geq \mathrm{Const}\cdot\mu^2(U)\cdot S\cdot\log n, \] where \(S\) is the number of nonzero components in \(x^0\), and \(\mu\) is the largest entry in \(U\) properly normalized: \(\mu(U) = \sqrt{n} \cdot \max_{k,j} |U_{k,j}|\). The smaller \(\mu\), the fewer samples needed. The result holds for ``most'' sparse signals \(x^0\) supported on a fixed (but arbitrary) set \(T\). Given \(T\), if the sign of \(x^0\) for each nonzero entry on \(T\) and the observed values of \(Ux^0\) are drawn at random, the signal is recovered with overwhelming probability. Moreover, there is a sense in which this is nearly optimal since any method succeeding with the same probability would require just about this many samples.