PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparsity-Cognizant Total Least-Squares for Perturbed Compressive Sampling

Hao Zhu, Geert Leus, Georgios B. Giannakis

arXiv:1008.2996v1cs.IT

TL;DR

The paper addresses sparse linear regression when perturbations affect both measurements and the regression matrix, a setting not handled jointly by standard sparsity methods or TLS. It develops sparse TLS formulations and near-optimum or reduced-complexity solvers, with weighted and structured extensions. Analysis and simulations demonstrate practical impact in cognitive-radio sensing and robust direction-of-arrival estimation.

  • Problem

    Existing sparsity-based regression methods do not account for regression-matrix perturbations, while TLS does not account for sparsity in under-determined models.

  • Method

    The paper formulates sparse TLS optimization problems and develops near-optimum, reduced-complexity, weighted, and structured S-TLS solvers.

  • Results

    Analysis and simulations demonstrate the practical impact of the S-TLS framework relative to BP, Lasso, and TLS alternatives.

  • Takeaways & Limitations

    S-TLS extends TLS to sparse, partially or fully perturbed, over- or under-determined linear models and supports applications involving basis mismatch.

Abstract

from arXiv · show

Solving linear regression problems based on the total least-squares (TLS) criterion has well-documented merits in various applications, where perturbations appear both in the data vector as well as in the regression matrix. However, existing TLS approaches do not account for sparsity possibly present in the unknown vector of regression coefficients. On the other hand, sparsity is the key attribute exploited by modern compressive sampling and variable selection approaches to linear regression, which include noise in the data, but do not account for perturbations in the regression matrix. The present paper fills this gap by formulating and solving TLS optimization problems under sparsity constraints. Near-optimum and reduced-complexity suboptimum sparse (S-) TLS algorithms are developed to address the perturbed compressive sampling (and the related dictionary learning) challenge, when there is a mismatch between the true and adopted bases over which the unknown vector is sparse. The novel S-TLS schemes also allow for perturbations in the regression matrix of the least-absolute selection and shrinkage selection operator (Lasso), and endow TLS approaches with ability to cope with sparse, under-determined "errors-in-variables" models. Interesting generalizations can further exploit prior knowledge on the perturbations to obtain novel weighted and structured S-TLS solvers. Analysis and simulations demonstrate the practical impact of S-TLS in calibrating the mismatch effects of contemporary grid-based approaches to cognitive radio sensing, and robust direction-of-arrival estimation using antenna arrays.

EDICS: SSP-SNMD, SSP-PARE, DSP-RECO, SAM-CALB, MLR-COGP

The paper acknowledges support from NSF and NWO-STW grants and notes an earlier presentation at an IEEE workshop.

  • The work was supported by four NSF grants and by NWO-STW under its VICI program.The listed NSF grants are CCF-0830480, CCF-1016605, ECCS-0824007, and ECCS-1002180; the NWO-STW project is 10382.
  • Part of the work was presented at the 11th IEEE International Workshop on Signal Processing Advances in Wireless Communications in 2010.The workshop took place in Marrakech, Morocco, June 20–23, 2010.
  • The authors are affiliated with the University of Minnesota and Delft University of Technology.

I. INTRODUCTION

The introduction identifies a gap between sparsity-based regression, which does not model matrix perturbations, and TLS, which does not handle sparse under-determined models. It presents sparse TLS as a framework addressing these settings, with extensions using perturbation prior information and applications in sensing and direction-of-arrival estimation.

  • Motivation and problem: Sparsity supports compressive sampling and sparse regression, but existing CS, BP, and Lasso methods do not account for perturbations in the equation matrix.These perturbations can reflect mismatch between an adopted basis and the actual unknown basis.
  • Motivation and problem: TLS fits fully perturbed linear models, but existing TLS approaches cannot consistently estimate under-determined systems or exploit sparsity in the unknown vector.
  • S-TLS framework: Sparse TLS (S-TLS) formulates sparse, perturbed linear-model fitting and supplies CS, BP, and Lasso-type algorithms for partially and fully perturbed models.
  • S-TLS framework: S-TLS provides sparsity-cognizant regularized TLS alternatives with consistent estimators for under-determined models without requiring prior perturbation information.
  • Extensions and evaluation: The framework also incorporates deterministic structure and perturbation statistics through weighted and structured S-TLS criteria and algorithms.
  • Extensions and evaluation: Simulations evaluate the novel weighted and structured S-TLS framework against BP, Lasso, and TLS in cognitive-radio sensing and direction-of-arrival estimation.

II. PRELIMINARIES AND PROBLEM STATEMENT

The paper addresses sparse linear models in which perturbations affect the data vector and regression matrix, extending compressive-sampling and Lasso formulations toward sparse total least squares. The problem is especially relevant under basis mismatch and under-determined errors-in-variables models.

  • Sparse recovery: Compressive sampling assumes a sparse coefficient vector in a known basis and can recover it by solving nonconvex ℓ0 or convex ℓ1 problems under suitable conditions.The sparse vector contains more than n−m zero elements at unknown entries.
  • Perturbed models: Perturbations in the data vector motivate BP/Lasso, but conventional sparse-recovery formulations do not account for perturbations in the regression matrix.Such matrix perturbations can arise from compressing-matrix disturbances, basis errors, or mismatch between adopted and actual bases.
  • Basis mismatch: Basis mismatch models the actual basis as B + EB, affecting grid-based localization, time-delay, frequency, and Doppler estimation.The resulting coefficient relationship is θo = (B + EB)xo with xo sparse.
  • Open problem: Prior analyses addressed reconstruction performance under matrix perturbations but provided no algorithms for sparse reconstruction in fully perturbed under-determined models.This leaves the algorithmic question of recovering sparse vectors while accounting for perturbations in y and/or A unresolved.
  • S-TLS formulation: The paper introduces sparse total least squares to account for sparsity and develop solvers for under-determined models perturbed in both the data and regression matrix.Its formulation includes y + e = (A + E)x with an ℓ1 sparsity penalty, and the objective is generally nonconvex because of Ex.
  • Scope: S-TLS is formulated to handle perturbations that may be random or deterministic, with or without known prior structure, and motivates weighted and structured extensions.The paper also considers broader extensions such as sparse matrix recovery and applications in antenna-array calibration and cognitive radio sensing.

III. MAP OPTIMALITY OF S-TLS FOR EIV MODELS

The paper establishes that S-TLS has a statistical optimality interpretation for perturbed errors-in-variables models under specified Gaussian and Laplacian assumptions. An equivalent reformulation supports this result and later solver development.

  • EIV model: The errors-in-variables model represents observed y and A as perturbations of an underlying system involving Ao, xo, ey, and EA.The perturbation vector is assumed i.i.d. Gaussian in the stated model assumptions.
  • Statistical assumptions: Under the first prior setting, xo has a Laplacian prior while Ao has an i.i.d. uniform non-informative prior; an alternative setting models Ao conditioned on xo with Gaussian rows.These assumptions connect sparsity-promoting priors with perturbed-regression modeling.
  • Equivalent formulations: Lemma 1 shows that the constrained S-TLS formulation is equivalent to one problem involving x and E and another fractional-form problem involving only x.The reformulation eliminates e using the model constraint and obtains the fractional form through a minimum-norm least-squares solution.
  • MAP optimality: Under the first prior setting, the x,E formulation is MAP optimal for estimating both xo and Ao.The result follows by combining the Gaussian perturbation likelihood with the Laplacian prior and uniform prior on Ao.
  • MAP optimality: Under the second prior setting, the fractional x-only formulation is MAP optimal for estimating xo while treating Ao as a nuisance parameter.The conditional Gaussian model yields the likelihood structure required for the fractional S-TLS criterion.
  • Generalization: The MAP optimality result is later generalized to structured and correlated perturbations with known covariance matrices.This extension motivates weighted and structured S-TLS formulations.

IV. S-TLS SOLVERS

The paper develops two iterative S-TLS solvers for the nonconvex sparse total-least-squares problem: a globally convergent near-optimum method and a lower-complexity local method. The former combines bisection with branch-and-bound, while the latter supports efficient initialization.

  • Solver overview: Two iterative algorithms solve the S-TLS problem: one approaches the global optimum, while the other guarantees convergence to a local optimum with lower computational demand.The first method is computationally demanding; the second is computationally efficient and can initialize the first.
  • Reduced-complexity solver: The reduced-complexity solver is important both as a standalone suboptimal method and as an initializer for the ε-optimal algorithm.This role reduces the number of expensive calls to the branch-and-bound inner solver.
  • Motivation: Unlike ordinary TLS, whose global optimization can use SVD, S-TLS lacks an efficient convex solver because its ℓ1-constrained criteria are nonconvex.This nonconvexity motivates the two-solver design and its performance-complexity trade-off.
  • Near-optimum solver: The near-optimum solver uses outer bisection and inner branch-and-bound iterations to optimize an equivalent constrained formulation.Bisection shrinks bounds on the fractional objective, while branch-and-bound bounds an indefinite quadratic surrogate over shrinking boxes.
  • Near-optimum solver: The bisection interval is successively reduced according to the sign of the inner optimum, yielding convergence to the global optimum of the constrained problem.The inner iterations use convex under-approximations to obtain lower bounds and constrained suboptimum solutions for upper bounds.
  • Inner optimization: The branch-and-bound inner loop handles an indefinite quadratic surrogate because its Hessian is not guaranteed to be positive or negative definite.A semidefinite program selects a diagonal matrix that makes the lower approximant convex over each box.
  • Convergence and complexity: Proposition 2 quantifies the outer iterations required to approach the global optimum within ε, while the inner bounds tighten as boxes are split or discarded.The box function is tailored to the ℓ1 constraint, but the branch-and-bound method has no guaranteed polynomial average complexity.

B. Alternating Descent Sub-Optimal Algorithm

The efficient S-TLS solver alternates updates of the perturbation matrix and sparse coefficient vector, using closed-form or Lasso-like subproblems. Its iterates converge monotonically to a stationary point, while simulations indicate the resulting local optimum is close to the global optimum.

  • Algorithmic structure: The alternating scheme cycles between estimating E with x fixed and estimating x with E fixed.The E update has a closed-form quadratic solution, while the x update is Lasso-like.
  • Initialization: Initializing E(0) = 0 yields x(0) as the Lasso estimate, providing an empirically supported starting point.Prior results reported accurate reconstruction even when both A and y are perturbed.
  • Convergence: The block coordinate descent iterates converge monotonically to at least a stationary point of the S-TLS problem from arbitrary initialization.The guarantee follows because each coordinate update reduces or preserves the cost.
  • Empirical quality: Simulations show that the local optimum reached by the efficient scheme is very close to the global optimum of the more complex method.This supports the computational appeal of the reduced-complexity solver.
  • Coefficient update: Coordinate descent solves the sparse coefficient update through scalar soft thresholding, with larger λ shrinking more entries to zero.LARS provides a solution path across λ, whereas coordinate descent is preferred when a single λ is selected by cross-validation.
  • Regularization extensions: Concave regularization can mitigate Lasso bias and more closely approximate the ℓ0 pseudonorm, while retaining fast convergence when initialized by Lasso.These penalties make the S-TLS cost nonconvex but are reported to yield improved estimates of x.

V. WEIGHTED AND STRUCTURED S-TLS

The weighted and structured S-TLS framework incorporates parsimonious structure and prior information about perturbations into sparse TLS estimation. Under stated rank and structural assumptions, it admits efficient formulations and a monotonically convergent alternating solver, with MAP optimality in the structured EIV model.

  • Structure model: A structure map S(p) represents [A y] through np parameters, enabling parsimonious descriptions when np ≪ m(n + 1).The framework also encompasses unstructured matrices by taking p as the vectorization of [A y].
  • Formulation: Weighted and structured S-TLS replaces unstructured perturbations with a parameterized structure and weights their perturbation vector by a positive definite matrix W.The unweighted structure-only case is recovered when W = I.
  • Structural reduction: Separable linear structure decouples perturbations in A and y, reducing the constraint to SA(I ⊗x)εA − Syεy = y −Ax.The resulting compact problem is minx,ε {ε^T W ε + λ∥x∥1} subject to G(x)ε = r(x).
  • Equivalent forms: The constrained WSS-TLS problem is equivalent to unconstrained nonconvex problems obtained by eliminating εy or all perturbation variables.These reductions support efficient solvers and optimality analysis.
  • Algorithm: The alternating WSS-TLS solver estimates x through an ℓ1-regularized convex subproblem and updates the perturbation vector in closed form.The x update is efficient because r(x) is linear in x, while the perturbation update is quadratic.
  • Convergence: The WSS-TLS iterates converge monotonically at least to a stationary point when Sy has full column rank.The paper notes that tall full-column-rank Sy matrices can also be handled with suitable weights.
  • Statistical optimality: Under assumptions (as1′) and (as2), WSS-TLS is the MAP-optimal estimator of xo and pA in the structured EIV model.This links the optimization criterion to statistical optimality under the stated model.

VI. S-TLS APPLICATIONS

The paper evaluates S-TLS in two sensing applications involving sparse-vector reconstruction with perturbations in the data matrix. In both applications, matrix perturbations arise from inaccurate modeling of the underlying true matrix.

  • Experimental scope: The application study demonstrates the practical impact of accounting for perturbations in the data matrix [A y].The experiments cover two sensing applications involving reconstruction of sparse vectors.
  • Perturbation model: In both applications, EA models inaccuracies in the underlying matrix Ao, while ey represents perturbations in the data vector.This establishes the perturbed data-matrix setting used in the application analyses.

A. Cognitive Radio Sensing

Cognitive-radio sensing estimates active-source locations and powers from PSD samples using a sparse grid-based linear model. The adopted sensing matrix is perturbed by grid mismatch, and WSS-TLS compensates for these errors.

  • Problem setup: The task is to estimate active-source locations and powers from power spectral density samples measured at cognitive-radio receivers.Candidate source locations are represented on a Cartesian grid.
  • Data construction: PSD samples are noise-compensated and collected into y, while receiver-specific model rows form A and noise terms form εy.The resulting dimensions include m = K N_r for y and n = N_b N_g for A.
  • Grid mismatch: The perturbation EA captures mismatch between the adopted grid and the inaccessible true matrix Ao, yielding a structured EIV model.The mismatch is represented through affine structure coefficients associated with source-location errors.
  • Interpretation: The coefficient vector xo encodes source powers, with its support identifying source locations.The sensing matrix columns collect products of channel gains and basis functions.
  • Sparsity model: The grid-based model is sparse because transmissions are narrowband and the number of active sources is much smaller than the number of grid points.Increasing grid density converts localization into a higher-dimensional linear estimation problem.
  • Method comparison: Existing BP/Lasso approaches do not account for gridding mismatch, whereas WSS-TLS compensates for grid-induced errors.Simulations report that sensing accuracy improves considerably when these errors are modeled and compensated.

B. DoA Estimation via Sparse Linear Regression

Sparse linear regression models DoA estimation using a grid-based array response, while S-TLS jointly estimates sparse support and grid-induced perturbations. This enables direct angle-error compensation and, in some cases, high-resolution single-step estimation.

  • Motivation: DoA estimation localizes sources from spatial samples collected across a possibly uncalibrated ULA.Existing subspace estimators require relatively many snapshots for reliable covariance estimation, especially with uncalibrated arrays.
  • Sparse linear model: The grid-based model represents each candidate direction with an array-response column and sparse coefficients identify active source locations.The response phase depends on antenna spacing, wavelength, and candidate angle.
  • Perturbation model: Errors-in-variables perturbations capture off-grid DoAs as well as antenna gain, phase, and position errors.The received snapshot follows yt = (A + EA)xo,t + (−ey,t), with EA representing regression-matrix mismatch.
  • Structured perturbations: For small angular mismatch, the actual array response is approximated linearly through a derivative-like perturbation column.This yields a structured array manifold Ao = A + EA.
  • S-TLS approach: Structured S-TLS jointly estimates the nonzero support and grid-induced perturbations, directly compensating angle errors.Unlike grid-refinement or MDL/interpolation remedies, the proposed approach performs the compensation within the estimation procedure.
  • S-TLS approach: The approach provides high-resolution DoA estimates in a single step and can, in certain cases, operate without multiple snapshots.Multiple snapshots are still expected to improve performance for matrix S-TLS.

VII. SIMULATED TESTS

Simulations evaluate S-TLS against global and local alternatives, Lasso, TLS, and regularized TLS in perturbed sparse regression and sensing applications. The tests report improved support recovery, source localization, and DoA estimation under matrix mismatch.

  • Optimization tests: As ε becomes smaller, the attained cost f(x) decreases monotonically and drops sharply to the genie-aided global minimum.Alternating descent performs comparably to the global algorithm and is therefore used in subsequent tests.
  • S-TLS versus Lasso: S-TLS improves over Lasso in estimation errors, especially ℓ0 error and recovery of the true support over moderate λ values.At high λ, both estimates approach the all-zero vector, making ℓ0 errors similar.
  • S-TLS versus TLS: ROC curves show that Lasso, and more clearly S-TLS, outperform TLS and regularized TLS in recovering the correct support.Detection probability measures correct identification of nonzero support, while false alarms measure incorrectly selected zero entries.
  • CR spectrum sensing: In cognitive-radio sensing, both Lasso and WSS-TLS identify the active frequency band, but WSS-TLS returns one source at [0.5 0.5] instead of four nearby grid sources.The true source is at [0.4 0.6], and WSS-TLS correctly identifies its position in the estimated PSD map.
  • DoA estimation: In DoA estimation, Lasso returns four entries around two sources, whereas WSS-TLS returns two grid estimates with perturbation estimates for angle correction.The corrected DoAs are formed as ˆϑs := ˆθg + ˆǫs_g.
  • DoA estimation: Monte Carlo variance curves confirm that WSS-TLS outperforms Lasso, while WSS-TLS identifies support without post-processing in a single step.The two WSS-TLS curves nearly coincide across the compared processing variants.

VIII. CONCLUDING REMARKS

The paper develops sparse total least-squares methods for fully perturbed, including under-determined, regression models. Analysis establishes optimality or convergence properties, while simulations demonstrate applications to cognitive-radio sensing and DoA estimation.

  • Contributions: S-TLS extends TLS by incorporating sparsity and handling perturbations in both the data and regression matrix.This includes compressive sampling, basis pursuit, and Lasso-style sparse regression under errors-in-variables models.
  • Contributions: The framework handles fully perturbed linear regression models and under-determined systems.This expands the traditional TLS setting beyond models with perturbations only in the data vector.
  • Algorithms: Near-optimum and reduced-complexity suboptimum solvers optimize generally nonconvex S-TLS criteria with convergence guarantees.The algorithms use bisection, branch-and-bound, or coordinate-descent iterations and apply to deterministic or random perturbation models.
  • Generalizations: Prior knowledge about perturbation structure or statistics yields weighted and structured S-TLS estimators, which are MAP-optimal under specific statistical models.Simulations corroborate the analytical claims and compare the estimators with competing alternatives.
  • Applications: Applications demonstrate practical impact for grid-based cognitive-radio sensing and DoA estimation with possibly uncalibrated antenna arrays.The reported experiments address mismatch effects in both application domains.
  • Future work: Future work includes performance analysis of the proposed algorithms and online implementations for optimal adaptive processing.These topics define explicit scope boundaries for the current study.

g of (12)

The figures compare optimization behavior, estimation errors, support recovery, and application-specific spatial or angular estimates for S-TLS and competing methods.

  • Algorithmic procedure: Algorithm 1-b uses bisection over a cost interval to produce an ε-optimal solution.Its stopping condition is based on the interval width ε.
  • Algorithmic procedure: The coordinate-descent algorithm alternates updates of coefficient entries and the perturbation iterate until convergence.It initializes the perturbation matrix and coefficient vector, then cycles residual, coefficient, and perturbation updates.
  • Application figures: Figure 1 depicts a grid with Ng = 25 candidate locations, Ns = 1 transmitting source, and Nr = 4 receiving CRs.The topology provides the spatial layout for the cognitive-radio sensing test.
  • Comparison figures: Figure 3 compares S-TLS and Lasso using ℓ2, ℓ1, and ℓ0 estimation errors, plus ROC curves against TLS and regularized TLS.The support-recovery comparison is the key reading of panel (d).
  • Application figures: Figure 4 compares Lasso and WSS-TLS spatial PSD maps for the CR network, with the marked point indicating the actual source location.The supported comparison is whether each map identifies the true source position.
  • Application figures: Figure 5 compares Lasso and WSS-TLS angular spectra with the actual pattern, and plots DoA-estimate variance versus SNR.The variance comparison includes WSS-TLS and Lasso with and without interpolation.
Loading 1008.2996v1…