In this paper, we prove that a 3 ρ -locally maximum volume submatrix A ^ ∈ R r × r in the matrix A ∈ R M × N can be found in O M N r log r + log ρ r operations, and a ρ -locally maximum volume submatrix for ρ ⩽ 3 can be found in O M N r 3 log ρ r operations. Based on these submatrices, it is possible to construct a rank revealing LU decomposition with guarantees for the approximation accuracy in spectral and Chebyshev norms.