  Let $A$ be a $n$ by $n$ matrix. A skeleton decomposition is any factorization
of the form $CUR$ where $C$ comprises columns of $A$, and $R$ comprises rows of
$A$. In this paper, we consider uniformly sampling $\l\simeq k \log n$ rows and
columns to produce a skeleton decomposition. The algorithm runs in $O(\l^3)$
time, and has the following error guarantee. Let $\norm{\cdot}$ denote the
2-norm. Suppose $A\simeq X B Y^T$ where $X,Y$ each have $k$ orthonormal
columns. Assuming that $X,Y$ are incoherent, we show that with high
probability, the approximation error $\norm{A-CUR}$ will scale with
$(n/\l)\norm{A-X B Y^T}$ or better. A key step in this algorithm involves
regularization. This step is crucial for a nonsymmetric $A$ as empirical
results suggest. Finally, we use our proof framework to analyze two existing
algorithms in an intuitive way.
