Encrypted SVD

Definition

The singular value decomposition factors a matrix $A$ of order $N$ as

where $U$ and $V$ are orthogonal and $\Sigma$ is diagonal, carrying the singular values

on its diagonal. The singular values are the nonnegative square roots of the eigenvalues of $A^{\top}A$ (equivalently $A A^{\top}$); they always exist and are real and nonnegative for any real matrix. This kernel takes an encrypted square matrix and returns its singular values.

Mathematical Domain

The decomposition is defined for matrices over the reals or complexes. Under a homomorphic scheme the entries are held encrypted; over the reals under CKKS the arithmetic is approximate, so the returned singular values are numerical approximations of the true ones.

Singular values are harder to obtain homomorphically than a matrix product because the classical algorithms rest on operations a homomorphic scheme does not provide natively: square roots, comparisons and sorting, normalization, and convergence tests. Approaches over encrypted data are therefore iterative and lean on polynomial approximations of these primitives, converging toward the singular values with repeated ring operations. The kernel prescribes no particular method; the number of steps and the accuracy reached depend on the technique and on the spectrum of $A$.

Parameters Defined by Specifications

A specification narrows the general operation into a concrete problem by fixing:

• the entry domain and homomorphic scheme (for example f64 under CKKS)
• the matrix order $N$ and its shape (here, square)
• which quantities are required — here the singular values only, not the factors $U$ and $V$
• any range or conditioning assumptions that make the accuracy well-defined
• the accuracy rule and how closeness is scored

Applications

Singular values drive principal-component analysis and dimensionality reduction, low-rank and best-rank-$k$ approximation, rank and condition-number estimation, total least squares, denoising, and recommendation systems. Computing them over encrypted data lets these analytics run on confidential matrices — feature tables, covariance data, or user–item ratings — without revealing the underlying data or its spectrum.