Practical Localization Algorithms

From CRB to Code

Sections 14.1-14.3 established the theoretical framework (FIM, CRB, multi-panel fusion). Section 14.4 bridges to practical algorithms: how to actually compute p^\hat{\mathbf{p}} from observed signals. The two dominant approaches are maximum likelihood estimation (MLE) and gradient-based optimization. Each has its tradeoffs.

Definition:

Maximum Likelihood Position Estimator

For observation y=heff(p)v+w\mathbf{y} = \mathbf{h}_{\text{eff}}(\mathbf{p})\mathbf{v} + \mathbf{w} with known RIS configuration Φ\boldsymbol{\Phi} and known pilot, the log-likelihood of p\mathbf{p} is

log⁡p(y∣p)=−12σ2∥y−heff(p)v∥2+const.\log p(\mathbf{y}|\mathbf{p}) = -\frac{1}{2\sigma^2}\|\mathbf{y} - \mathbf{h}_{\text{eff}}(\mathbf{p})\mathbf{v}\|^2 + \text{const}.

The MLE is

p^MLE=arg⁡min⁡p∥y−heff(p)v∥2.\hat{\mathbf{p}}^{\text{MLE}} = \arg\min_\mathbf{p} \|\mathbf{y} - \mathbf{h}_{\text{eff}}(\mathbf{p})\mathbf{v}\|^2.

For multi-RIS (multiple observations), the MLE minimizes the total squared error across all panels.

The MLE is consistent (converges to true position as SNR → ∞) and asymptotically efficient (achieves the CRB). In practice, it is the gold standard — all practical algorithms are approximations of it.

Newton Method for MLE Position Estimation

Complexity: O(T⋅N⋅k3)O(T \cdot N \cdot k^3) for kk-dim position; typical T=10T = 10-2020 iterations
Input: observations {ym}\{\mathbf{y}_m\}, pilots, RIS configurations.
Output: p^\hat{\mathbf{p}}.
1. Initialize p(0)\mathbf{p}^{(0)} (e.g., from single-panel trilateration
or coarse grid search).
2. For t=0,1,…t = 0, 1, \ldots:
3. \quad Compute log-likelihood gradient:
g(t)=∇plog⁡p(y∣p(t))\mathbf{g}^{(t)} = \nabla_\mathbf{p} \log p(\mathbf{y}|\mathbf{p}^{(t)}).
4. \quad Compute Hessian (negative FIM):
H(t)=−J(p(t))\mathbf{H}^{(t)} = -\mathbf{J}(\mathbf{p}^{(t)}).
5. \quad Newton step: p(t+1)=p(t)−H(t)−1g(t)\mathbf{p}^{(t+1)} = \mathbf{p}^{(t)} - \mathbf{H}^{(t)-1} \mathbf{g}^{(t)}.
6. \quad Check convergence: ∥g(t+1)∥<ϵ\|\mathbf{g}^{(t+1)}\| < \epsilon.
7. return p(T)\mathbf{p}^{(T)}.

Newton converges quadratically near the optimum — dramatic acceleration over gradient descent. Total compute: ~1-10 ms per position update on modern hardware. For Kalman-style tracking, each iteration is incremental and cheap.

Gradient Descent Position Estimator

Complexity: O(T⋅N)O(T \cdot N); slower convergence than Newton but simpler
Input: observations, initial position p(0)\mathbf{p}^{(0)}, step size μ\mu.
Output: p^\hat{\mathbf{p}}.
1. For t=0,1,…t = 0, 1, \ldots:
2. \quad Compute gradient g(t)=∇plog⁡p\mathbf{g}^{(t)} = \nabla_\mathbf{p} \log p.
3. \quad Update: p(t+1)=p(t)+μg(t)\mathbf{p}^{(t+1)} = \mathbf{p}^{(t)} + \mu \mathbf{g}^{(t)}.
4. \quad Armijo line search if needed.
5. \quad Check convergence.
6. return p\mathbf{p}.

Gradient descent is the fallback when Newton is ill-conditioned (low SNR, degenerate geometry). More robust to bad initializations but slower.

The Initialization Problem

Both MLE algorithms require a good initial guess p(0)\mathbf{p}^{(0)}. Poor initialization can converge to a local minimum (especially when the log-likelihood is non-convex globally). Strategies:

  1. Coarse grid search: evaluate log-likelihood on a grid of candidate positions; pick the best as initial guess.
  2. Single-panel far-field: one panel gives AOA; the UE is on a cone. Multiple panels intersect cones → rough position.
  3. Previous estimate (Kalman tracking): use previous position
    • motion model as initial guess.
  4. Machine learning: train a neural network to estimate position from raw observations; use as initial guess for MLE refinement.

A well-initialized MLE converges in a few iterations; a poorly- initialized one can fail entirely.

MLE Convergence: Newton vs. Gradient Descent

Compare convergence trajectories of Newton and gradient-descent position estimators. Newton takes ∼5\sim 5-1010 iterations; gradient descent takes ∼50\sim 50-100100. At low SNR, gradient descent is more robust.

Parameters
128
10
30
1
⚠️Engineering Note

RIS Positioning Deployment

Practical RIS localization deployment:

  1. Panel geometry calibration: one-time precise measurement of RIS element positions at deployment. Errors <1< 1 mm in panel geometry give clean positioning.
  2. Pilot protocol: known pilot signal transmitted by UE; BS correlates through the RIS. Typical pilot length: 10-100 symbols per position update.
  3. Update rate: depends on UE mobility. Stationary: ∼1\sim 1 Hz (every 1 s). Pedestrian: ∼10\sim 10 Hz. Robotic manipulation: ∼100\sim 100-10001000 Hz (challenging).
  4. Multi-user: each UE gets its own pilot slot. KK users × τ\tau symbols each = KτK\tau total pilot overhead.
  5. Fallback: if positioning fails (insufficient SNR, geometry degeneracy), fall back to GPS or visual odometry. Don't rely solely on RIS positioning in safety-critical applications.
Practical Constraints
  • •

    Position accuracy target: ∼1\sim 1 cm (indoor), ∼10\sim 10 cm (outdoor mmWave), ∼0.1\sim 0.1 mm (sub-THz).

  • •

    Update rate: ∼10\sim 10-100100 Hz typical; ∼1000\sim 1000 Hz for robotic applications.

  • •

    Pilot overhead: ∼1\sim 1-5%5\% of coherence block for continuous tracking.

  • •

    Initial position ambiguity: resolve via grid search or multi-panel triangulation.

Common Mistake: Calibration Is Everything

Mistake:

"Install the RIS panel; start positioning with default parameters."

Correction:

Panel geometry calibration is foundational. Errors in element positions (sub-mm accuracy required at mmWave) directly propagate to positioning errors. A 1-mm element-position error produces a ∼1\sim 1-mm UE positioning error. Phase calibration is equally important: per-element phase offsets must be characterized (usually via a known reference transmitter). Skipping calibration results in positioning accuracies that are 10-100x worse than predicted. Budget time and instrumentation for calibration at deployment.

Near-Field RIS Positioning

Animation showing the near-field wavefront curvature reaching a RIS panel. Different RIS elements see the UE at different distances — the resulting quadratic phase pattern encodes both angle and distance. Shows how the Fisher Information Matrix is constructed from per-element phase observations.

Fisher Information Matrix (FIM)

The matrix J(θ)=E[∇log⁡p(y∣θ)∇Tlog⁡p(y∣θ)]\mathbf{J}(\boldsymbol{\theta}) = \mathbb{E}[\nabla \log p(y|\boldsymbol{\theta}) \nabla^T \log p(y|\boldsymbol{\theta})] quantifying how much information an observation yy carries about the parameter θ\boldsymbol{\theta}. Its inverse lower-bounds the covariance of any unbiased estimator (Cramér-Rao bound).

Related: CRB Scaling with NN, Newton Method for MLE Position Estimation

Near-Field Localization

Position estimation exploiting wavefront curvature. When the UE is within the Fraunhofer distance DF=2L2/λD_{\text{F}} = 2L^2/\lambda of a large aperture, the per-element phase contains a quadratic term in distance, enabling 3D position estimation from a single panel.

Related: Fraunhofer Distance, Xl Mimo

Quick Check

With a single near-field RIS panel of NN elements, the position Cramér-Rao bound σp\sigma_p scales with NN as:

σp∝1/N\sigma_p \propto 1/\sqrt{N}

σp∝1/N\sigma_p \propto 1/N

σp∝1/N2\sigma_p \propto 1/N^2

σp\sigma_p is independent of NN

Correction:
σp∝1/N\sigma_p \propto 1/N

Each added element contributes coherent phase information; the FIM grows as N2N^2 (aperture scaling) so σp2∝1/N2\sigma_p^2 \propto 1/N^2, giving σp∝1/N\sigma_p \propto 1/N.

Why This Matters: RIS-Positioning for 6G

6G targets sub-meter indoor positioning as a native capability. Industrial automation, XR, and vehicular-x demand continuous location tracking even in GPS-denied NLoS environments. RIS makes this achievable cheaply: a single RIS-aided anchor plus a UE provides cm-level localization via near-field curvature (no multiple anchors required). ETSI GR RIS 002 already mentions positioning as a priority application. The CommIT multi-RIS fusion algorithm (Caire-Atzeni 2023) is a candidate for standardization.

Multi-RIS Position FusionChapter Summary