Making Every Bit Count for $A$-Optimal State Estimation

1. Problem Statement

The paper addresses the problem of optimal bit allocation for Linear Minimum Mean Square Error (LMMSE) state estimation in systems with heterogeneous sensor measurements under a global communication bandwidth constraint.

• Context: In modern sensing networks (e.g., power grids with Advanced Metering Infrastructure), sensors often have limited bandwidth. Measurements are quantized, introducing noise. The variance of this quantization noise depends on the number of bits allocated to each sensor.
• Objective: The goal is to distribute a fixed total bit budget ($B$) across $m$ sensors to minimize the trace of the error covariance matrix of the LMMSE estimator. This is known as an A-optimal design criterion.
• Challenge:
  • The relationship between bit allocation ($b_i$) and measurement precision ($\rho_i$) is exponential: $\rho_i = \kappa_i 4^{b_i}$.
  • While the objective function is convex with respect to precision variables ($\rho$), the budget constraint becomes non-convex in the log-domain of $\rho$.
  • Conversely, in the bit domain ($b$), the feasible set (simplex) is convex, but the objective function becomes non-convex due to the exponential reparameterization.
  • The problem is an integer programming problem, which is NP-hard.

2. Methodology

The authors propose a two-stage approach: solving a continuous relaxation of the problem and then rounding the solution to integers.

A. Mathematical Formulation

• Measurement Model: Quantized measurements are modeled as $y = Hx + z$, where $z$ is additive noise with covariance $D = \text{diag}(d_1, \dots, d_m)$. The variance $d_i$ is inversely proportional to $4^{b_i}$.
• Relaxed Problem: The integer constraint $b \in \mathbb{Z}_+^m$ is relaxed to $b \in \mathbb{R}_+^m$ with the constraint $\sum b_i \le B$.
• Gradient Derivation: A key theoretical contribution is the derivation of a closed-form gradient for the objective function $F(b) = \text{tr}(C_\epsilon(b))$.
  • The gradient is given by: $\nabla F(b) = -(\ln 4) \rho(b) \odot [h_i^\top C_\epsilon(b)^2 h_i]_{i=1}^m$.
  • Computational Efficiency: Evaluating this gradient requires only a single Cholesky factorization of the information matrix $M(b)$, costing $O(d^3)$, rather than computing full matrix products.

B. Optimization Algorithms

Two algorithms are developed to solve the continuous relaxation:

1. Frank-Wolfe (FW) Method (First-Order):

   • Oracle: The Linear Minimization Oracle (LMO) for the simplex constraint has a closed-form solution. It simply selects the sensor with the most negative gradient component and allocates the entire budget to it (a vertex of the simplex).
   • Convergence: The authors prove that the FW gap converges to zero at a rate of $O(1/\sqrt{T})$, providing a computable convergence certificate.
   • Advantage: Memory efficient; does not require storing a Hessian approximation.

2. Interior Point Method (Second-Order):

   • Solver: Uses the Ipopt solver with the analytic gradient derived above.
   • Hessian Approximation: Instead of computing the exact Hessian (which is expensive), it uses a Limited-Memory BFGS (L-BFGS) approximation.
   • Performance: Typically converges in fewer iterations (20–50) compared to FW but requires more memory for the Hessian approximation.

C. Rounding Procedure

To recover integer bit allocations from the continuous solution $\bar{b}$:

• Largest Remainder Rounding: The authors propose a solver-agnostic rounding algorithm.
  1. Take the floor of the continuous solution: $\lfloor \bar{b} \rfloor$.
  2. Calculate the residual budget $R_{rem} = B - \sum \lfloor \bar{b} \rfloor$.
  3. Distribute the remaining $R_{rem}$ bits to the sensors with the largest fractional parts of $\bar{b}$.
• Theoretical Guarantee: The paper provides a bound on the quality gap between the rounded integer solution and the continuous optimum, proving the solution is feasible and the error is bounded by the Lipschitz constant of the gradient.

3. Key Contributions

1. Non-Convex A-Optimal Formulation: Formulated the heterogeneous bit allocation problem as a non-convex optimization problem over a convex polytope, distinct from standard sensor selection problems.
2. Analytic Gradient & Cholesky Reduction: Derived a gradient formula that reduces computational cost to a single Cholesky factorization per iteration, enabling scalability.
3. Algorithmic Framework:
   • A Frank-Wolfe algorithm with a closed-form LMO and a proven $O(1/\sqrt{T})$ convergence rate.
   • An Interior Point Method accelerated by L-BFGS.
4. Rounding with Guarantees: Introduced a largest remainder rounding procedure with a theoretical bound on the sub-optimality gap.
5. Empirical Validation: Demonstrated significant performance gains over uniform bit allocation in power grid scenarios.

4. Numerical Results

Experiments were conducted on IEEE power grid test cases (ranging from 14 to 300 buses) and synthetic datasets.

• Solver Performance:

  • Speed: The Frank-Wolfe method was significantly faster for large-scale problems (e.g., 300 buses) because it avoids the memory overhead of Hessian approximations and scales linearly with the number of sensors ($m$) in the "sensor-rich" regime.
  • Convergence: The Interior Point method (Ipopt) converged in fewer iterations (20–50) but failed to converge within time limits for very large instances where $m/d$ (sensor-to-state ratio) was high.
  • Gradient Impact: Both solvers relied heavily on the analytic gradient; without it, performance degraded drastically.

• Heterogeneous vs. Uniform Allocation:

  • In bandwidth-constrained regimes (low bits per sensor, e.g., 2–3 bits), heterogeneous allocation outperformed uniform allocation by 47% to 53% in reducing the estimation error (trace of covariance).
  • As bandwidth increased (e.g., >5 bits per sensor), the performance gap diminished, as the system became less constrained.
  • The improvement was most pronounced when the optimizer could concentrate bits on high-information sensors.

• Rounding Quality:

  • The actual error gap between the rounded integer solution and the continuous optimum was found to be orders of magnitude smaller than the theoretical worst-case bound (e.g., $10^{-6}$ vs. theoretical bound), indicating the bound is conservative but the method is robust.

5. Significance

This work bridges the gap between information theory (quantization noise) and control theory (state estimation) under resource constraints.

• Practical Impact: It provides a rigorous method for designing communication-constrained sensor networks (like smart grids), showing that intelligently allocating bits based on sensor importance yields massive accuracy improvements compared to standard uniform allocation.
• Theoretical Contribution: It demonstrates that non-convex problems with convex feasible sets can be efficiently solved using first-order methods (Frank-Wolfe) when a closed-form LMO exists, offering a viable alternative to second-order methods for large-scale systems.
• Scalability: The reduction of gradient computation to a single Cholesky factorization makes the approach applicable to large-scale power grids and sensor networks where previous methods were computationally prohibitive.