  In this paper, we present a Rank Revealing Randomized Singular Value
Decomposition (R3SVD) algorithm to incrementally construct a low-rank
approximation of a potentially large matrix while adaptively estimating the
appropriate rank that can capture most of the actions of the matrix. Starting
from a low-rank approximation with an initial guessed rank, R3SVD adopts an
orthogonal Gaussian sampling approach to obtain the dominant subspace within
the leftover space, which is used to add up to the existing low-rank
approximation. Orthogonal Gaussian sampling is repeated until an appropriate
low-rank approximation with satisfactory accuracy, measured by the overall
energy percentage of the original matrix, is obtained. While being a fast
algorithm, R3SVD is also a memory-aware algorithm where the computational
process can be decomposed into a series of sampling tasks that use constant
amount of memory. Numerical examples in image compression and matrix completion
are used to demonstrate the effectiveness of R3SVD in low-rank approximation.
