The quaternion CUR (qCUR) matrix decomposition constructs low-rank approximations of quaternion matrices by selecting a few key rows and columns, yet existing qCUR approximation methods typically fail to provide tight error bounds. This work focuses on constructing qCUR via leverage score sampling, and derives novel gap error bounds for the rank-k qCUR decomposition: we leverage real representations of quaternion random matrices (which connect these matrices to probability theory) to synthesize the combined impacts of column and row selection strategies, and the derived bound intrinsically ties the decomposition’s approximation accuracy to the decay rate of the matrix’s singular values. Specifically, when sampling is performed on the p (<InlineEquation ID="IEq1"> <EquationSource Format="TEX">$p\ge k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>) exact dominant singular vectors, the rank-k approximation exhibits a relative error (relative to the best rank-k approximation error) of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O\left( \varepsilon {\sigma _{p+1}^2}/{\sigma _{k+1}^2}\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <mi>ε</mi> <msubsup> <mi>σ</mi> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </msubsup> <mo stretchy="false">/</mo> <msubsup> <mi>σ</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </msubsup> </mfenced> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\sigma _j$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>σ</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> denotes the j-th largest singular value and the number of selected columns and rows satisfies <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$c, r = O\left( {p\log p}/{\varepsilon }\right) $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>,</mo> <mi>r</mi> <mo>=</mo> <mi>O</mi> <mfenced close=")" open="("> <mrow> <mi>p</mi> <mo>log</mo> <mi>p</mi> </mrow> <mo stretchy="false">/</mo> <mi>ε</mi> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. The approximation error is further analyzed for cases where the leverage score is computed based on approximate dominant singular vectors from randomized quaternion singular value decomposition. Empirical results on various classes of synthetic data and real-world color image completion tasks show that our algorithm outperforms the qCUR variants with squared-length sampling or the discrete empirical interpolation method.

Leverage score-based quaternion CUR decomposition: Gap error analysis and applications

期刊论文
发表日期：

2026年4月15日

查看全文

Qiaohua Liu,
Jiehui Gu

摘要

The quaternion CUR (qCUR) matrix decomposition constructs low-rank approximations of quaternion matrices by selecting a few key rows and columns, yet existing qCUR approximation methods typically fail to provide tight error bounds. This work focuses on constructing qCUR via leverage score sampling, and derives novel gap error bounds for the rank-k qCUR decomposition: we leverage real representations of quaternion random matrices (which connect these matrices to probability theory) to synthesize the combined impacts of column and row selection strategies, and the derived bound intrinsically ties the decomposition’s approximation accuracy to the decay rate of the matrix’s singular values. Specifically, when sampling is performed on the p ( $p\ge k$ $p \geq k$ ) exact dominant singular vectors, the rank-k approximation exhibits a relative error (relative to the best rank-k approximation error) of $O\left( \varepsilon {\sigma _{p+1}^2}/{\sigma _{k+1}^2}\right) $ $O (ε σ_{p + 1}^{2} / σ_{k + 1}^{2})$ , where $\sigma _j$ $σ_{j}$ denotes the j-th largest singular value and the number of selected columns and rows satisfies $c, r = O\left( {p\log p}/{\varepsilon }\right) $ $c, r = O (p log p / ε)$ . The approximation error is further analyzed for cases where the leverage score is computed based on approximate dominant singular vectors from randomized quaternion singular value decomposition. Empirical results on various classes of synthetic data and real-world color image completion tasks show that our algorithm outperforms the qCUR variants with squared-length sampling or the discrete empirical interpolation method.