PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Driven Sparse Sensor Placement for Reconstruction

Krithika Manohar, Bingni W. Brunton, J. Nathan Kutz, Steven L. Brunton

arXiv:1701.07569v2math.OCeess.SY

TL;DR

Sparse sensor placement must preserve reconstruction accuracy while limiting sensor count. This paper uses data structure to select informative sensors and reports that tailored-basis sensing typically reconstructs more accurately with far fewer measurements than compressed sensing.

Abstract

from arXiv · show

Optimal sensor placement is a central challenge in the design, prediction, estimation, and control of high-dimensional systems. High-dimensional states can often leverage a latent low-dimensional representation, and this inherent compressibility enables sparse sensing. This article explores optimized sensor placement for signal reconstruction based on a tailored library of features extracted from training data. Sparse point sensors are discovered using the singular value decomposition and QR pivoting, which are two ubiquitous matrix computations that underpin modern linear dimensionality reduction. Sparse sensing in a tailored basis is contrasted with compressed sensing, a universal signal recovery method in which an unknown signal is reconstructed via a sparse representation in a universal basis. Although compressed sensing can recover a wider class of signals, we demonstrate the benefits of exploiting known patterns in data with optimized sensing. In particular, drastic reductions in the required number of sensors and improved reconstruction are observed in examples ranging from facial images to fluid vorticity fields. Principled sensor placement may be critically enabling when sensors are costly and provides faster state estimation for low-latency, high-bandwidth control. MATLAB code is provided for all examples.

Compressed sensing: Random measurements in a universal basis

This section examines sparse signal reconstruction through low-dimensional measurements, including compressed sensing in a universal basis and data-driven sensor selection tailored to known patterns. It covers sparse-coefficient recovery and conditions for compressed-sensing recovery, alongside sensor selection from features extracted from representative training data.

Compressed sensing: Random measurements in a universal basis

  • Images and audio are sparse in Fourier or wavelet bases, and compressed sensing infers sparse coefficients from a low-dimensional subsample.These bases underlie JPEG and MP3 compression, respectively.Source: Compressed sensing: Random… · p. 5

Theory of compressed sensing

  • For p < n, the system is underdetermined with infinitely many solutions, so compressed sensing seeks the sparsest solution consistent with the measurements.The figure describes compressed sensing as providing the sparsest solution to an underdetermined linear system.Source: Theory of compressed sensing · p. 6, Figure 1 · p. 6
  • Compressed-sensing recovery requires incoherent measurements and a sufficient measurement count; less coherent measurements require fewer measurements.The stated count condition involves K log(n/K), multiplied by a small constant multiple of incoherence.Source: Theory of compressed sensing · p. 6
  • Random-projection incoherence is not optimal, full-state random projections may be difficult to obtain physically, and QR pivot locations fail to identify an unknown signal’s sparse structure.The text says this is why QR pivot locations cannot be used as optimized sensors for compressed sensing.Source: Theory of compressed sensing · p. 7

Compressed sensing example

Optimal sparse sensing in a tailored basis

  • When signal type is known, optimized sensors can be tailored to the signals of interest using low-rank features mined from representative training data.The passage identifies proper orthogonal decomposition (POD) as one way to extract these features.Source: Optimal sparse sensing in a tailored… · p. 8
  • The section focuses on data-driven sensor selection and explores sparse, convex, and greedy optimization methods for solving it.It frames this as a generalized sensor-selection method connecting empirical interpolation with experimental-design approaches.Source: Optimal sparse sensing in a tailored… · p. 8
  • QR pivoting is fast and simple to implement, and provides nearly optimal sensors tailored to a data-driven POD basis.The generalized selection method connects empirical interpolation and QR pivoting to condition-number optimization and D-optimal experimental design.Source: Optimal sparse sensing in a tailored… · p. 8

Proper orthogonal decomposition

This section develops data-driven sensor placement for reconstruction from a POD-based, training-data-tailored low-dimensional representation, introducing QR-based greedy selection and extending Q-DEIM to oversampled placement. It relates QR pivoting and matrix-volume objectives to D-optimal experimental design and discusses the computational tradeoffs of practical sensor-selection methods.

Proper orthogonal decomposition

  • Projecting states into the POD subspace yields a reduced representation for tasks costly in the full state space, including time-stepping, parameter estimation, and control.For time-series data, time-varying POD coefficients separate space and time, so POD should be used carefully for traveling-wave data.Source: Proper orthogonal decomposition · p. 9
  • POD derives orthonormal modes as the left singular vectors of the state-observation matrix, providing a low-dimensional embedding for high-dimensional states.POD coefficients provide the reduced representation, which can be lifted to the full state by a linear combination of the modes.Source: Proper orthogonal decomposition · pp. 9–10
  • Choosing POD rank without magnifying noise is difficult; in practice, rank is often selected by thresholding singular values to capture a chosen share of data variance.An optimal hard threshold criterion is described for additive Gaussian white noise of unknown variance and is reported effective even when the noise is likely not Gaussian.Source: Proper orthogonal decomposition · p. 10

Sensor placement for reconstruction

  • Sensor placement optimizes point measurements to recover modal coefficients from a tailored basis, with conditioning important because it governs error amplification and signal-to-noise degradation.The measurement matrix is Θ = CΨr; its condition number is therefore desirable to control through row selection.Source: Sensor placement for reconstruction · pp. 10–11
  • An approximate greedy solution using matrix QR factorization addresses sensor placement’s otherwise intractable combinatorial search.The placement problem seeks measurements that permit the best reconstruction, and the proposed approach approximates its solution.Source: Sensor placement for reconstruction · p. 12
  • The reconstruction sensor-placement discussion builds on Q-DEIM.Source: Sensor placement for reconstruction · p. 12

Sparse sensor placement with QR pivoting

  • The proposed extension handles p > r by applying pivoted QR to the POD basis to select sensors that condition the sampled basis.The work identifies this oversampled case as an original contribution.Source: Sparse sensor placement with QR pivoting · p. 12
  • One O(n^3) QR factorization produces a hierarchical list of all n pivots, allowing sensor counts to reuse prefixes instead of recomputing selection.The oversampled case has storage requirements that scale quadratically with state dimension.Source: Sparse sensor placement with QR pivoting · p. 13

Relation to optimal experimental design

  • The matrix-volume objective is identical to D-optimal experiment design for selecting p of n candidate experiments in a low-dimensional subspace.Source: Relation to optimal experimental design · p. 14
  • Exact optimal-design solutions are intractable, so sensor selection generally uses heuristics such as convex relaxation with a linear sensor constraint.The passage identifies convex relaxation as a common approach to the optimization problem.Source: Relation to optimal experimental design · p. 14
  • A sidebar notes that QR pivoting fails to exploit sparsity, although it can efficiently find a sparse solution to an underdetermined linear system.The passage gives y = Θs as the system form and identifies MATLAB's backslash command as a way to apply the method.Source: Relation to optimal experimental design · p. 15
  • Convex optimization and semidefinite-program methods are more computationally expensive than QR pivoting, which requires one matrix factorization overall.The comparison attributes the higher cost to work performed at each iteration of the optimization methods.Source: Relation to optimal experimental design · p. 15
  • EIM and QR are practical for sensor placement across many candidate locations on fine spatial grids and are methods of choice in reduced-order modeling.Source: Relation to optimal experimental design · p. 16

Comparison of methods

This section compares QR-based sensor placement with compressed sensing, DEIM, convex optimization, and POD across facial-image, cylinder-flow, and SST examples, examining reconstruction, sensor requirements, computational cost, and measurement noise.

Comparison of methods

  • Across examples, QR-pivot sensors in tailored bases outperform random compressed-sensing measurements and require many fewer sensors for equal reconstruction performance.The comparison covers fluid dynamics, facial images, and ocean surface temperatures.Source: Comparison of methods · p. 16
  • For a well-scoped reconstruction task with sufficient training data, the authors advocate principled sensor selection over compressed sensing.The section notes potential reductions in sensor purchasing, placement, and maintenance costs, as well as computation latency.Source: Comparison of methods · p. 16

Flow past a cylinder

  • In the cylinder-flow data, the first 42 POD modes capture nearly all system energy, and optimized sensing remains orders of magnitude more accurate than random sensing.The figure reports that minimal QR sensors recover nearly as well as the snapshot approximation in the same POD basis; overfitting occurs beyond rank 42.Source: Flow past a cylinder · p. 18, Figure F5 · p. 18
  • At p = 2r, oversampled QR reduces reconstruction error 4x versus DEIM; at p = r = 40, DEIM and Q-DEIM perform comparably, with a slight improvement for QR.The figure also states that all sampling methods remain within a constant factor of the optimal POD approximation with full states as sensor noise increases.Source: Figure 5 · p. 19

Noise comparison study

  • The study evaluates selection criteria alongside A-, D-, and E-optimal experimental-design criteria for estimation with zero-mean white noise, assumed only in test measurements and not training.The sensor sets are trained on the first 100 snapshots and used to reconstruct the remaining 50 validation snapshots.Source: Noise comparison study · p. 19
  • QR reconstruction is slightly more accurate than DEIM and competitive in both speed and accuracy; QR factorization is significantly faster than convex optimization methods.Source: Noise comparison study · pp. 19–20
  • QR pivoting achieves a 4x smaller reconstruction error than DEIM in the noise comparison study.Source: Noise comparison study · p. 20

Extended Yale B eigenfaces

  • 50 QR-selected pixels (5% of all pixels) surpass compressed sensing with 300 random pixels, while compressed sensing requires 600 pixels for comparable recovery.Random-sensor least-squares reconstruction is consistently poor.Source: Figure 7 · p. 21, Extended Yale B eigenfaces · p. 21
  • QR sensors cluster around the eyes, nose, and mouth, enabling adequate facial reconstruction with as few as 166 sensors, or 16% of pixels.The passages report no meaningful facial structure beyond eigenface 166.Source: Figure 7 · p. 21, Extended Yale B eigenfaces · p. 21
  • The Extended Yale B eigenface result’s dropoff is slower than cylinder flow’s because its decay is slower.Source: Extended Yale B eigenfaces · p. 22

Sea surface temperature (SST)

  • QR-selected sensors clearly identify the ENSO feature, while 100 eigensst modes sufficiently recover dynamics and additional modes refine convective phenomena.The QR sensor locations are informative about ocean dynamics, including ENSO off coastal Peru.Source: Sea surface temperature (SST) · p. 22, Figure 10 · p. 23
  • POD’s time-invariant, variance-based modes have difficulty separating intermittent, isolated low-energy temporal events such as El Niño.Reordering snapshots does not change its dominant modes.Source: Sea surface temperature (SST) · p. 22
  • Tensor decompositions and temporal-frequency methods such as multiresolution dynamic mode decomposition have identified El Niño where POD failed, but sensor selection using their non-normal modes remains open.Source: Sea surface temperature (SST) · p. 22
  • For a single snapshot, QR-selected sensors filter uninformative features and achieve better reconstruction; random sensors perform poorly with least-squares (ℓ2) reconstruction and compressed sensing.Increasing POD modes only marginally improves full-state modal approximation. ℓ2 reconstruction suffers from overfitting with both random and, to a lesser extent, QR sensors.Source: Figure 11 · p. 23
  • Compressed sensing uses random measurements and sparsity-promoting ℓ1 minimization for unknown underdetermined signals, whereas tailored data-driven sensing uses optimized samples equal to intrinsic rank r.Although compressed sensing can recover a wider range of signals, data-driven sensing can drastically reduce sensor requirements and downstream computation for structured physical systems.Source: Sea surface temperature (SST) · p. 24

Discussion

The discussion contrasts optimized sensing in a data-driven tailored basis with random sensing in a universal basis. Tailored sensing typically reconstructs more accurately with about half as many sensors, but the appropriate strategy depends on the task and its constraints.

Discussion

  • No single sparse-sensing strategy fits every high-dimensional system; the choice depends on training-data availability, task scope, sensor cost, and computation latency.The discussion divides methods into optimized sensing in a data-driven tailored basis and random sensing in a universal basis.Source: Discussion · p. 24
  • Optimized tailored-basis sensing is suited to tightly scoped reconstruction when sufficient training data are available.The authors advocate principled sensor selection over compressed sensing under those conditions.Source: Discussion · pp. 24–25
  • Random sensing in a universal basis requires more sensors for accurate reconstruction but makes fewer assumptions about the signal and is more general..Source: Discussion · pp. 24–25
  • Tailored-basis optimized sensing typically reconstructs more accurately than random measurements while reducing the sensor count by about a factor of two.The authors also report that tailored-basis sensor selection and reconstruction are computationally efficient and simple to implement, whereas compressed sensing generally requires a costly iterative algorithm.Source: Discussion · p. 25
  • Pivoted-QR sensors can also be used with known non-data-driven bases, such as polynomials or radial basis functions, and can generalize across dynamical regimes.The passage conditions this use on known signal structure.Source: Discussion · p. 25

Potential applied impact

  • For costly-sensor applications, obtaining the training data needed to optimize sensor placement may be difficult; with noisy measurements, ignoring uninformative sensors may improve reconstruction.The discussion notes that high-fidelity simulations or large-scale surveys may be needed to obtain training data.Source: Potential applied impact · p. 25
  • Selecting a small subset of key pixels can speed computation and reduce power consumption.This is relevant to applications with readily available sensors but limited computational or battery resources, including mobile control and monitoring.Source: Potential applied impact · p. 25

Reproducible Research

A Matlab code supplement supports reproducing the manuscript’s results with datasets and scripts to recreate result figures.

Reproducible Research

Related papers

Loading 1701.07569v2…