Point cloud (PC)—a collection of discrete geometric samples of a 3D object’s surface—is typically large, which entails expensive subsequent operations. Thus, PC sub-sampling is of practical importance. Previous model-based sub-sampling schemes are ad-hoc in design and do not preserve the overall shape sufficiently well, while previous data-driven schemes are trained for specific pre-determined input PC sizes and sub-sampling rates and thus do not generalize well. Leveraging advances in graph sampling, we propose a fast PC sub-sampling algorithm of linear time complexity that chooses a 3D point subset while minimizing a global reconstruction error. Specifically, to articulate a sampling objective, we first assume a super-resolution (SR) method based on feature graph Laplacian regularization (FGLR) that reconstructs the original high-res PC, given points chosen by a sampling matrix <inline-formula><tex-math notation="LaTeX">${\mathbf H}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">H</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq1-3143089.gif"/></alternatives></inline-formula>. We prove that minimizing a worst-case SR reconstruction error is equivalent to maximizing the smallest eigenvalue <inline-formula><tex-math notation="LaTeX">$\lambda _{\min }$</tex-math><alternatives><mml:math><mml:msub><mml:mi>λ</mml:mi><mml:mo movablelimits="true" form="prefix">min</mml:mo></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq2-3143089.gif"/></alternatives></inline-formula> of matrix <inline-formula><tex-math notation="LaTeX">${\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}$</tex-math><alternatives><mml:math><mml:mrow><mml:msup><mml:mrow><mml:mi mathvariant="bold">H</mml:mi></mml:mrow><mml:mi>⊤</mml:mi></mml:msup><mml:mi mathvariant="bold">H</mml:mi><mml:mo>+</mml:mo><mml:mi>μ</mml:mi><mml:mi mathvariant="script">L</mml:mi></mml:mrow></mml:math><inline-graphic xlink:href="dinesh-ieq3-3143089.gif"/></alternatives></inline-formula>, where <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\mathcal{L}}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">L</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq4-3143089.gif"/></alternatives></inline-formula> is a symmetric, positive semi-definite matrix derived from a neighborhood graph connecting the 3D points. To arrive at a fast algorithm, instead of maximizing <inline-formula><tex-math notation="LaTeX">$\lambda _{\min }$</tex-math><alternatives><mml:math><mml:msub><mml:mi>λ</mml:mi><mml:mo movablelimits="true" form="prefix">min</mml:mo></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq5-3143089.gif"/></alternatives></inline-formula>, we maximize a lower bound <inline-formula><tex-math notation="LaTeX">$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}})$</tex-math><alternatives><mml:math><mml:mrow><mml:msubsup><mml:mi>λ</mml:mi><mml:mo movablelimits="true" form="prefix">min</mml:mo><mml:mo>-</mml:mo></mml:msubsup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mrow><mml:mi mathvariant="bold">H</mml:mi></mml:mrow><mml:mi>⊤</mml:mi></mml:msup><mml:mi mathvariant="bold">H</mml:mi><mml:mo>+</mml:mo><mml:mi>μ</mml:mi><mml:mi mathvariant="script">L</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="dinesh-ieq6-3143089.gif"/></alternatives></inline-formula> via selection of <inline-formula><tex-math notation="LaTeX">${\mathbf H}$</tex-math><alternatives><mml:math><mml:mi mathvariant="bold">H</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq7-3143089.gif"/></alternatives></inline-formula>—this translates to a graph sampling problem for a signed graph <inline-formula><tex-math notation="LaTeX">${\mathcal G}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">G</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq8-3143089.gif"/></alternatives></inline-formula> with self-loops specified by graph Laplacian <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\mathcal{L}}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">L</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq9-3143089.gif"/></alternatives></inline-formula>. We tackle this general graph sampling problem in three steps. First, we approximate <inline-formula><tex-math notation="LaTeX">${\mathcal G}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">G</mml:mi></mml:math><inline-graphic xlink:href="dinesh-ieq10-3143089.gif"/></alternatives></inline-formula> with a balanced graph <inline-formula><tex-math notation="LaTeX">${\mathcal G}_B$</tex-math><alternatives><mml:math><mml:msub><mml:mi mathvariant="script">G</mml:mi><mml:mi>B</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq11-3143089.gif"/></alternatives></inline-formula> specified by Laplacian <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\mathcal{L}}}_B$</tex-math><alternatives><mml:math><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>B</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq12-3143089.gif"/></alternatives></inline-formula>. Second, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we perform a similarity transform <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\mathcal{L}}}_p~=~{\mathbf S}{\boldsymbol{\mathcal{L}}}_B {\mathbf S}^{-1}$</tex-math><alternatives><mml:math><mml:mrow><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mspace width="3.33333pt"/><mml:mo>=</mml:mo><mml:mspace width="3.33333pt"/><mml:mi mathvariant="bold">S</mml:mi><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>B</mml:mi></mml:msub><mml:msup><mml:mrow><mml:mi mathvariant="bold">S</mml:mi></mml:mrow><mml:mrow><mml:mo>-</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:math><inline-graphic xlink:href="dinesh-ieq13-3143089.gif"/></alternatives></inline-formula>, so that all Gershgorin disc left-ends of <inline-formula><tex-math notation="LaTeX">${\boldsymbol{\mathcal{L}}}_p$</tex-math><alternatives><mml:math><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>p</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq14-3143089.gif"/></alternatives></inline-formula> are aligned exactly at <inline-formula><tex-math notation="LaTeX">$\lambda _{\min }({\boldsymbol{\mathcal{L}}}_B)$</tex-math><alternatives><mml:math><mml:mrow><mml:msub><mml:mi>λ</mml:mi><mml:mo movablelimits="true" form="prefix">min</mml:mo></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>B</mml:mi></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="dinesh-ieq15-3143089.gif"/></alternatives></inline-formula>. Finally, we choose samples on <inline-formula><tex-math notation="LaTeX">${\mathcal G}_B$</tex-math><alternatives><mml:math><mml:msub><mml:mi mathvariant="script">G</mml:mi><mml:mi>B</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="dinesh-ieq16-3143089.gif"/></alternatives></inline-formula> using a previous graph sampling algorithm to maximize <inline-formula><tex-math notation="LaTeX">$\lambda ^-_{\min }({\mathbf H}^{\top } {\mathbf H}+ \mu {\boldsymbol{\mathcal{L}}}_p)$</tex-math><alternatives><mml:math><mml:mrow><mml:msubsup><mml:mi>λ</mml:mi><mml:mo movablelimits="true" form="prefix">min</mml:mo><mml:mo>-</mml:mo></mml:msubsup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mrow><mml:mi mathvariant="bold">H</mml:mi></mml:mrow><mml:mi>⊤</mml:mi></mml:msup><mml:mi mathvariant="bold">H</mml:mi><mml:mo>+</mml:mo><mml:mi>μ</mml:mi><mml:msub><mml:mi mathvariant="script">L</mml:mi><mml:mi>p</mml:mi></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math><inline-graphic xlink:href="dinesh-ieq17-3143089.gif"/></alternatives></inline-formula> in linear time. Experimental results show that 3D points chosen by our algorithm outperformed competing schemes both numerically and visually in reconstruction quality.