$p$-adic Principal Component Analysis

This paper formulates a $p$-adic optimization problem for matrix factorization and investigates a heuristic method analogous to Principal Component Analysis (PCA) to solve it.

The Gist

Imagine you are a detective trying to solve a mystery in a city where the rules of distance and geometry are completely different from our own. In our world (the "Real" world), if you want to understand a crowd of people, you might group them by height, weight, or hair color to find the main patterns. This is what Principal Component Analysis (PCA) does in standard data science: it simplifies complex data by finding the most important "directions" or "features" that explain the most variation.

But what if your data isn't made of smooth, continuous numbers like height or weight? What if your data is made of categories (like "Yes/No," "Red/Blue/Green") or numbers that wrap around like a clock (like time on a 12-hour clock)? Standard PCA struggles here because it tries to force these distinct categories into a smooth line, losing the unique "flavor" of the data.

Enter Tomoki Mihara's paper on p-adic PCA. He proposes a new way to analyze this kind of "categorical" or "modular" data using a mathematical tool called p-adic numbers.

Here is the breakdown of the paper using simple analogies:

1. The Problem: The Wrong Map for the Terrain

Imagine you have a map of a city where the streets are arranged in a perfect grid (like a chessboard). If you try to navigate this city using a map designed for a winding, hilly countryside (standard Real numbers), you will get lost. You might think two houses are close because they are next to each other on the map, but in reality, they are on opposite sides of a wall.

• The Issue: Standard PCA treats data like a smooth, continuous fluid. But categorical data (like Boolean logic: True/False) is more like a digital switch or a clock. It has "gaps" and "jumps."
• The Solution: The author suggests using p-adic numbers. Think of p-adic numbers as a different kind of ruler. Instead of measuring how far apart two things are by the straight line between them, p-adic numbers measure how similar their "inner structure" is. Two numbers are "close" in p-adic land if they share the same ending digits (like how 123 and 223 are close because they both end in 23).

2. The New Tool: "Nearest Neighbor" instead of "Perpendicular"

In standard PCA, the magic trick is finding perpendicular lines (like the x-axis and y-axis on graph paper). You project data onto these lines to see the main patterns.

• The Problem: In the p-adic world, the concept of "perpendicular" (using a dot product) breaks down. It's like trying to use a compass to find North in a place where magnetic north doesn't exist.
• The Innovation: The author invents a new definition of "orthogonality" (independence). Instead of asking "Are these lines at a 90-degree angle?", he asks: "Is this point the closest possible point to that line?"
  • Analogy: Imagine you are trying to describe a complex shape. Instead of drawing lines at 90-degree angles, you keep finding the "closest" simple shape that fits the data, subtract it, and then look at what's left. You repeat this until you've captured the main structure.

3. The Method: Two Ways to Build the Map

The paper proposes two specific algorithms (methods) to do this p-adic dimensionality reduction:

A. The "Greedy" Approach (Non-Reduced PCA)

• How it works: It looks at the data and picks the very first interesting piece it sees, uses that as a guide, subtracts it out, and moves to the next piece.
• The Flaw: It's a bit hasty. Because it doesn't plan ahead, the "guide lines" it picks might overlap or interfere with each other, like trying to build a house by just stacking bricks without checking if they are level.
• Best for: When you want to be very careful not to make false alarms (False Positives).

B. The "Planner" Approach (Reduced PCA)

• How it works: Before it starts building, it takes a step back and organizes the whole pile of data first. It cleans up the data, removes the overlaps, and creates a perfect, non-interfering set of guide lines before it starts the main analysis.
• The Benefit: This creates a much cleaner, more accurate map. It's like an architect drawing a blueprint before laying a single brick.
• Best for: Finding the true patterns and spotting anomalies (things that don't fit).

4. The Experiment: Finding the "Imposters"

The author tested these methods on a "Anomaly Detection" task. Imagine you have a warehouse full of identical-looking boxes (Normal Data), but a few of them are actually filled with gold bricks (Anomalies).

• The Challenge: In standard math, if the gold boxes are heavy, you can just weigh them. But in this p-adic world, the "weight" (size) of the gold boxes might look exactly the same as the normal boxes because of how the numbers wrap around.
• The Result:
  • The "Planner" (Reduced PCA) was incredibly good at spotting the gold boxes. It could see the subtle structural differences that the "Greedy" method missed.
  • It succeeded in finding the "imposters" even when standard mathematical tricks (like Smith Normal Form, which is the p-adic equivalent of standard Gaussian elimination) failed completely.

5. Why This Matters

This paper is a bridge between pure mathematics and practical data science.

• For Mathematicians: It solves a hard problem: "How do you do PCA when the geometry is weird and broken?"
• For Data Scientists: It offers a new tool for analyzing categorical data (like survey answers, DNA sequences, or boolean logic) without forcing them into a shape they don't belong in.

In a nutshell:
The author realized that trying to analyze categorical data with standard tools is like trying to measure a digital clock with a ruler. He built a new "p-adic ruler" and a new way to find the "main directions" of the data. His experiments show that this new method is excellent at spotting the "odd ones out" in complex, categorical datasets, outperforming older, more rigid mathematical techniques.

Technical Summary

Here is a detailed technical summary of the paper "p-adic Principal Component Analysis" by Tomoki Mihara.

1. Problem Statement

The paper addresses the challenge of performing dimensionality reduction and feature extraction on categorical or algebraic data that possesses a structure incompatible with standard Euclidean spaces ($\mathbb{R}^D$).

• Limitations of Standard PCA: Traditional PCA relies on linear algebra over $\mathbb{R}$, specifically the diagonalization of covariance matrices and the use of gradients. These methods fail in the $p$-adic setting ($\mathbb{Q}_p^D$ or $\mathbb{Z}_p^D$) because:
  • Symmetric matrices are not necessarily diagonalizable in $\mathbb{Q}_p$.
  • There is no natural $p$-adic analogue of the normal distribution to justify covariance-based approaches.
  • The standard inner product does not satisfy non-degeneracy ($\langle v, v \rangle = 0 \not\Rightarrow v = 0$).
  • Loss functions involving $p$-adic absolute values are discontinuous and locally constant almost everywhere, making gradient-based optimization (like Newton's method) inapplicable.
• The Gap: While methods like Smith Normal Form (based on the $\ell_\infty$-norm) exist for matrix factorization over rings, they are unsuitable for anomaly detection tasks where anomalies might have smaller norms than normal data. The paper seeks a heuristic method for $p$-adic matrix factorization using the $\ell_q$-norm ($q \in [1, \infty)$) that respects the algebraic structure of the data.

2. Methodology

The author formulates a $p$-adic PCA based on a geometric definition of orthogonality rather than an inner product.

A. $p$-adic Orthogonality

Instead of using an inner product, orthogonality is defined via the nearest neighbor property in a metric space.

• Definition: A vector $\vec{w}$ is the $\vec{v}_1$-component of $\vec{v}_0$ if $\vec{w}$ is the nearest neighbor of $\vec{v}_0$ in the subspace spanned by $\vec{v}_1$ (minimizing the $\ell_q$-norm distance).
• Orthogonal Component: $\vec{v}_0$ is orthogonal to $\vec{v}_1$ if $\vec{v}_0 - \vec{w} = \vec{v}_0$ (i.e., the projection is zero).
• Algorithmic Implementation: Finding the optimal scalar $c$ to minimize $\|\vec{v}_0 - c\vec{v}_1\|$ is solved using a Trie Tree (Prefix Tree) algorithm. The algorithm exploits the $\pi$-adic expansion of $p$-adic numbers to perform a depth-first search for the optimal coefficient modulo $p^E$.

B. Orthogonalization Systems

Since $p$-adic orthogonality is not symmetric and does not form a linear subspace, the Gram-Schmidt process does not apply directly.

• Iterated Orthogonalization: The paper proposes an iterative algorithm (Algorithm 5) where vectors are repeatedly orthogonalized against each other until the system stabilizes or a threshold is reached. This creates an "approximately orthogonal" system.

C. Two Variants of $p$-adic PCA

The paper introduces two heuristic approaches to solve the low-rank approximation problem (minimizing $\sum \|\vec{y}_i - \sum c_{d,i}\vec{x}_d\|$):

1. Non-reduced $p$-adic PCA (NRPCA):

   • Strategy: Greedily selects the first non-zero data vector from the input set as the next basis vector.
   • Pros: Fast, low false positive rate.
   • Cons: The resulting basis is not orthogonal; redundancy may reduce approximation quality.

2. Reduced $p$-adic PCA (RPCA):

   • Strategy: First, performs an Iterated Orthogonalization on the entire dataset to create a pre-computed, approximately orthogonal coordinate system ($Z$). Then, it selects basis vectors from this pre-computed system.
   • Pros: Produces a more orthogonal basis, leading to better low-rank approximations and higher true positive rates in anomaly detection.
   • Cons: Higher computational cost due to the pre-computation step.

D. Verification via Line Search

To verify if a solution is locally optimal, the paper defines a $p$-adic Line Search (and Coordinate Descent). This iteratively updates the coefficient matrix $C$ by projecting residuals onto the current basis vectors until no further loss reduction is possible. Experiments showed that the heuristic solutions (especially RPCA) were already close to locally optimal, requiring minimal further refinement.

3. Key Contributions

1. Formulation of $p$-adic PCA: The first formulation of a PCA-like dimensionality reduction method specifically for $p$-adic vector spaces ($\mathbb{Q}_p^D$ and $\mathbb{Z}_p^D$) that does not rely on diagonalization or gradients.
2. Geometric Orthogonality: The introduction of a robust definition of orthogonality based on nearest neighbors and the development of an iterative orthogonalization algorithm to handle the non-symmetric nature of $p$-adic geometry.
3. Algorithmic Efficiency: The use of Trie Trees to efficiently solve the $p$-adic optimization sub-problem (finding the best scalar projection) in integer arithmetic, avoiding numerical instability.
4. Anomaly Detection Framework: Demonstrating that $p$-adic PCA, particularly using the $\ell_q$-norm, is effective for anomaly detection in unsupervised settings where standard $\ell_\infty$-based methods (like Smith Normal Form) fail.

4. Experimental Results

The author tested NRPCA and RPCA on synthetic datasets with $p=7$, dimension $D=100$, and varying anomaly rates ($r$).

• Scenario 1: Open Balls (Clustering):

  • Normal data was distributed in disjoint closed balls; anomalies were scattered.
  • RPCA Performance: Achieved very high True Positive Ratios (detecting anomalies) and low False Positive Ratios when the number of clusters ($B$) was less than the target dimension ($D^-$). It successfully distinguished "significant" components (even balls) from anomalies, even when anomalies had large $\ell_\infty$ norms.
  • NRPCA Performance: Showed lower False Positive ratios (fewer false alarms) but lower detection rates for anomalies compared to RPCA.
  • Failure Case: When $B > D^-$ (more clusters than dimensions), performance degraded, as expected for dimensionality reduction.

• Scenario 2: Affine Subspaces:

  • Normal data lay on a low-dimensional affine subspace with noise; anomalies were off-subspace.
  • RPCA Performance: Consistently achieved near-perfect True Positive Ratios ($>96\%$) across all tested dimensions ($D'=10, 30$) and anomaly rates ($r=1, 10$).
  • Significance: RPCA succeeded in detecting anomalies even when the intrinsic dimension of the normal data ($D'$) exceeded the target reduction dimension ($D^-$), a scenario where linear algebraic methods (like Gauss elimination or Smith Normal Form) theoretically fail because they cannot distinguish noise from anomalies based solely on $\ell_\infty$ norms.

5. Significance and Conclusion

• Bridging Algebra and Statistics: The paper successfully bridges the gap between algebraic number theory ($p$-adic numbers) and statistical machine learning (dimensionality reduction). It provides a tool to analyze data with inherent algebraic structures (e.g., boolean data, modular arithmetic) without forcing them into a Euclidean embedding that destroys their structure.
• Anomaly Detection: The results suggest that $p$-adic PCA is a powerful tool for unsupervised anomaly detection, particularly in scenarios where anomalies do not simply have "larger" values than normal data (a common failure point for $\ell_\infty$-based methods).
• Future Applications: The methodology opens the door for applying $p$-adic optimization to other machine learning tasks, such as $p$-adic neural networks and clustering, where the discrete, totally disconnected nature of $p$-adic spaces better models certain types of categorical or hierarchical data.

In summary, Mihara presents a mathematically rigorous and computationally feasible heuristic for $p$-adic PCA, proving its utility in extracting meaningful low-dimensional structures from high-dimensional $p$-adic data.