PaperlayerView exact revision on arXiv

Source-linked AI summary

Tensor denoising with trend filtering

Francesco Ortelli, Sara van de Geer

arXiv:2101.10692v1math.STstat.TH

TL;DR

Tensor denoising seeks to recover a signal from Gaussian-noise observations. The paper extends trend filtering with kth-order Vitali total variation and reports an almost parametric reconstruction bound under piecewise-polynomial structure.

  • Problem

    Tensor denoising aims to recover an underlying tensor from observations corrupted by i.i.d. Gaussian noise.

    Source: §1 · p. 3

  • Method

    A regularized least-squares estimator uses the kth-order Vitali total variation of candidate-estimator differences, extending trend filtering to tensors.

    Source: §1 · p. 3

  • Results

    For tensors that are products of polynomials on a constant number of hyperrectangles, the normalized squared error is O(log^2 n/n) with high probability.

    Source: §9 · p. 37

  • Takeaways & Limitations

    An ANOVA decomposition connects lower-dimensional margin results to denoising the whole tensor.

    Source: §9 · p. 37

    The interpolating-tensor construction is not shown to work for general k; its suitability remains open beyond k in {1, 2, 3, 4}.

    Source: §9 · p. 37

Abstract

from arXiv · show

We extend the notion of trend filtering to tensors by considering the $k^{\rm th}$-order Vitali variation, a discretized version of the integral of the absolute value of the $k^{\rm th}$-order total derivative. We prove adaptive $\ell^0$-rates and not-so-slow $\ell^1$-rates for tensor denoising with trend filtering. For $k=\{1,2,3,4\}$ we prove that the $d$-dimensional margin of a $d$-dimensional tensor can be estimated at the $\ell^0$-rate $n^{-1}$, up to logarithmic terms, if the underlying tensor is a product of $(k-1)^{\rm th}$-order polynomials on a constant number of hyperrectangles. For general $k$ we prove the $\ell^1$-rate of estimation $n^{- \frac{H(d)+2k-1}{2H(d)+2k-1}}$, up to logarithmic terms, where $H(d)$ is the $d^{\rm th}$ harmonic number. Thanks to an ANOVA-type of decomposition we can apply these results to the lower dimensional margins of the tensor to prove bounds for denoising the whole tensor. Our tools are interpolating tensors to bound the effective sparsity for $\ell^0$-rates, mesh grids for $\ell^1$-rates and, in the background, the projection arguments by Dalalyan et al.

1 Introduction

The introduction frames tensor denoising as recovery of a signal from Gaussian-noise observations and presents kth-order Vitali TV regularization as an adaptive tensor extension of trend filtering. It motivates adaptation through structured sparsity, an ANOVA decomposition, and bounds for lower-dimensional margins.

1.1 TV regularization

  • A regularized signal approximator combines least-squares fit with a penalty; choosing a difference operator yields TV regularization, with different operators defining different TV notions.The paper considers discretizations of total kth-order derivatives for continuous images.Source: §1.1 · p. 4

1.2 Literature review: adaptive results for TV regularization

  • Earlier adaptivity results covered settings such as one-dimensional trend filtering and two-dimensional first-order Vitali TV; this paper treats kth-order Vitali TV for k=1, 2, 3, 4 in general dimension.The authors identify prior one-dimensional results [14] and two-dimensional results [16] as special cases of their results.Source: §1.2 · pp. 4–5

1.3 Adaptation for structured problems

  • Adaptation is expressed through an oracle inequality whose remainder must vanish; the effective sparsity depends on the penalty operator and active set.The authors use projection arguments to permit a tuning parameter smaller than the universal choice, and use an interpolating tensor to bound effective sparsity.Source: §1.3 · pp. 5–6

1.4 ANOVA decomposition

  • An ANOVA-type decomposition splits a tensor into mutually orthogonal components, including lower-dimensional margins that are polynomial of order at most k−1 along selected coordinates.The 0-dimensional margins are estimated by ordinary least squares, while l-dimensional margins are estimated with l-dimensional Vitali TV regularization.Source: §1.4 · pp. 6–7

1.5 Contributions

  • The contributions combine interpolating tensors, general antiprojection bounds, and ANOVA decomposition to establish risk bounds for tensor denoising.The authors also extend mesh-grid arguments to general dimension and order for not-so-slow ℓ1 rates.Source: §1.5 · p. 7

1.6 Organization of the paper

  • The paper proceeds from the estimator and adaptive and ℓ1-rate results to lower-dimensional margins, then applies those results to denoising the whole tensor.Sections 4–8 derive the synthesis form, prove adaptivity, apply general ℓ1-rate results, define margins, and establish whole-tensor bounds.Source: §1.6 · pp. 7–8

2 Model, notation and estimator

The model observes a tensor plus independent Gaussian noise with known variance and estimates the underlying signal using a kth-order Vitali TV-regularized estimator. The section defines the tensor operations, difference penalty, and active sets used to specify that estimator.

2 Model, notation and estimator

  • The model observes a d-dimensional tensor Y=f^0+ε with independent N(0,σ²) entries and known variance σ.The goal is to estimate f^0 from these noisy observations.Source: §2 · p. 8

2.1.1 Tensors with product structure

  • A tensor has product structure when each entry factors into one value from each of d coordinate vectors.The paper also uses entrywise multiplication for tensors with product structure.Source: §2.1.1 · p. 9

2.1.2 Orthogonality between tensors

  • Two tensors are orthogonal when the sum of their entrywise products is zero; for product-structured tensors, orthogonality in at least one coordinate implies tensor orthogonality.The entrywise product is described as the tensor analogue of a scalar product.Source: §2.1.2 · p. 9

2.1.3 Linear subspaces and orthogonal projections

  • For a linear subspace W, P_W denotes orthogonal projection onto W, while A_W=I−P_W projects onto its orthogonal complement.The notation also splits a tensor into its projected component and residual.Source: §2.1.3 · p. 9

2.2 Estimator

  • The kth-order Vitali TV sums the absolute total kth-order differences, and the estimator regularizes least-squares fit with this penalty and tuning parameter λ.The total difference operator discretizes the total kth-order derivative and includes an n^(k−1) normalization factor.Source: §2.2 · p. 10

2.3 Active sets

  • An active set S records selected indices of the total-difference tensor, and its size s is the number of those indices.The notation separates tensor entries on S from those outside S.Source: §2.3 · p. 10

3 Contributions

The paper extends trend filtering to tensors and establishes adaptive ℓ0- and ℓ1-rate results. It also extends ANOVA decomposition to kth-order differences, allowing margin results to yield bounds for whole-tensor estimation.

3 Contributions

  • The kth-order Vitali total variation extends trend filtering to d-dimensional tensors using Vitali variation and total discrete derivatives.The paper proves adaptive ℓ0-rates for k = 1, 2, 3, 4 and not-so-slow ℓ1-rates for tensor denoising.Source: §3 · p. 11
  • For ℓ0-rates, results for k = 1, 2, 3, 4 are proved, while sufficient conditions for general k remain open to verification in general.The paper notes that rates for d = 1 and k = 1, 2, 3, 4, and for d = 2 and k = 1, were already known; other stated cases are new contributions.Source: §3 · p. 11
  • The ℓ1-rates are described as not-so-slow, but whether they are minimax for d ≥ 2, modulo logarithmic terms, remains open.The contribution passage identifies results for d = 2, k ≥ 2, and d ≥ 3 as new.Source: §3 · p. 11
  • The extension of ANOVA decomposition to kth-order differences transfers d-dimensional margin results to lower-dimensional margins and yields ℓ0- and ℓ1-rate bounds for the whole tensor.Source: §3 · p. 11
  • The results recover previous trend-filtering and image-denoising results as special cases [14] [16].Source: §3 · p. 11

3.1 Preview of the results

  • Theorem 3.1 previews an adaptive ℓ0-rate for k = 1, 2, 3, 4 using an active set that defines a regular grid; its exponent examples are shown in Table 1.The theorem setup specifies an arbitrary g and an active set S of size s; the supplied excerpts do not include the rate expression.Source: §3.1 · pp. 11–12, Table 1 · p. 12
  • Table 2 gives examples of the exponent of n in Theorem 3.2's ℓ1-rate.The preview also gives examples of the exponent of s in Theorem 3.1's rate in Table 1.Source: Table 1 · p. 12, Table 2 · p. 13, §3.1 · p. 13

4 Synthesis form

The synthesis form represents the trend-filtering estimator using a dictionary of tensors with product structure. The dictionary links discrete truncated monomials to difference operators and supports approximation steps in the rate proofs.

4 Synthesis form

  • The estimator can be constructed as a linear combination of tensors with product structure whose factors are truncated monomials of order k − 1.The paper calls this collection the dictionary.Source: §4 · p. 13

4.2 Dictionary for general d

  • The d-dimensional dictionary is formed from tensors with product structure, extending the one-dimensional construction.Source: §4 · p. 13, §4.2 · p. 15

4.1 Dictionary for d = 1

  • In one dimension, the original dictionary contains n linearly independent discrete monomials: the first k have orders 0 through k − 1, and the remaining n − k are truncated monomials of order k − 1.Source: §4.1 · p. 14
  • The paper introduces a partially orthonormalized one-dimensional dictionary, again described as a collection of n linearly independent vectors.Source: §4.1 · p. 14
  • The one-dimensional dictionary is related to the difference operator, and the paper uses this relation with a Moore-Penrose pseudoinverse result to obtain a synthesis form.Source: §4.1 · p. 14

4.2 Dictionary for general d

  • The dictionary specifies the estimator's construction and facilitates approximation of orthogonal projections used in the adaptive ℓ0- and not-so-slow ℓ1-rate proofs.Source: §4.2 · p. 15

5 Adaptivity

Section 5 develops adaptive estimation of a tensor’s d-dimensional margin using effective-sparsity bounds from interpolating tensors, deriving the required weights and verifying the construction for k = 1, 2, 3, and 4. The proof also relates the dimensionality effect in the rate exponent to hyperrectangle side lengths and uses orthogonal projections for the empirical-process argument with uncorrelated errors.

5.1 Main result

  • Theorem 5.2 establishes adaptive estimation of the d-dimensional margin by trend filtering for k in {1, 2, 3, 4}.Its statement considers an arbitrary tensor and active set, subject to the theorem’s tuning conditions.Source: §5.1 · p. 17
  • For a regular-grid active set, choosing x and t of order log n recovers Theorem 3.1, with λ of order s^(-2k-1).The passage states that the regular grid permits this choice of λ.Source: §5.1 · p. 18

5.3 Effective sparsity via interpolating tensors

  • Interpolating tensors extend the effective-sparsity technique to tensors by matching jump signs while keeping entries off the enlarged active set bounded by one minus their noise weights.Bounding effective sparsity is sufficient for adaptation, and the interpolating-tensor lemma supplies such a bound.Source: Moreover we write · p. 19, §5.3 · p. 20

5.5 Antiprojections, inverse scaling factor and noise weights

  • The construction requires valid antiprojection bounds and noise weights, which determine the inverse scaling factor and constrain the interpolating tensor.The section gives lemmas establishing valid bounds on antiprojections and valid noise weights, then uses them to verify the constructed interpolating tensors.Source: §5.4 · p. 21, §5.5 · pp. 21–22, §5.6 · p. 23

5.6.1 Matching derivatives

  • Derivative matching constructs piecewise-polynomial interpolants with k − 1 continuous derivatives and piecewise-constant kth derivatives, designed to interpolate jump signs between locations and rectangle boundaries.Monotonicity and endpoint constraints keep their magnitudes bounded by one; the noise weights impose additional constraints on the construction.Source: §5.6.1 · pp. 23–24

5.6.2 Show a bound on the effective sparsity

  • The effective-sparsity bound accommodates the worst-case sign configuration, and for a regular-grid active set it yields a bound of the stated order.The construction assumes monotone interpolants; the section checks monotonicity analytically for k = 1, 2, 3 and computationally for k = 4.Source: §5.6.2 · p. 25

5.7 Proof of Theorem 5.2

  • The proof combines the general adaptive bound with the effective-sparsity result, after verifying the interpolant’s monotonicity and compliance with the noise-weight constraints.The constructed tensor has the valid form established earlier, enabling the application of Theorem A.1.Source: §5.7 · p. 27
  • Idempotence of orthogonal projections lets the proof work with uncorrelated errors by restricting tensors to an orthogonal subspace, enabling arguments of Ortelli and van de Geer [14].The cited Theorem 2.2 uses empirical-process increment bounds for i.i.d. errors; the proof adapts those arguments to its projected setting.Source: §5.7 · p. 28
  • The exponent of s reflects a bound involving the sum of hyperrectangle side lengths, rather than their product, which would scale with volume.The proof says it cannot bound the noise weights proportionally to hyperrectangle volume; volume scales as s^-1, while side length scales as s^-1/d.Source: §5.7 · p. 28

6 Not-so-slow ℓ1-rates

The section uses mesh-grid active sets to shorten maximal antiprojection lengths, which determine the inverse scaling factor in the not-so-slow rate argument. It then compares the resulting rate behavior with regular-grid active sets.

6 Not-so-slow ℓ1-rates

  • Mesh-grid active sets shorten maximal antiprojection lengths, the criterion used to choose the active set and reduce the inverse scaling factor.The inverse scaling factor is the maximal length of a dictionary atom’s antiprojection onto atoms indexed by the active set.Source: §6 · pp. 28–29

6.1 Mesh grids

  • A mesh grid is enlarged to accommodate higher-order trend filtering, with the original and enlarged sets having comparable cardinalities.The section illustrates a mesh grid for d = 2 and an enlarged mesh grid for d = 2 and k = 2.Source: §6.1 · p. 29, Figure 2 · p. 30, Figure 3 · p. 30

6.2 The inverse scaling factor when ˜S is an enlarged mesh grid

  • For an enlarged mesh grid, the section derives a smaller inverse-scaling-factor bound than for an enlarged regular grid.This bound is the basis for using mesh grids to improve the rate argument.Source: §6.2 · p. 30

6.3 Proof of Theorem 3.2

  • For fixed k, the slow rate approaches n^-1/2 log^1/2(n) as d grows, while for fixed d it approaches n^-1 as k grows.The regular-grid rate is slower than the mesh-grid rate; H(d) ≤ d for all d ≥ 1.Source: §6.3 · p. 31

7 Denoising lower-dimensional margins

The section handles lower-dimensional tensor margins by decomposing the tensor into mutually orthogonal marginal spaces and applying lower-dimensional trend filtering. The resulting margin-wise rates can be combined to estimate the whole tensor.

7 Denoising lower-dimensional margins

  • Least-squares estimation of the residual component can yield a rate of order n^-1/d, which is limiting when d ≥ 2.The section motivates decomposing that component into lower-dimensional marginal spaces.Source: §7 · p. 31

7.1 Margins as lower dimensional objects

  • The tensor is decomposed into mutually orthogonal marginal spaces, and lower-dimensional versions of trend filtering are applied to those margins.The ANOVA decomposition organizes the tensor into these orthogonal components.Source: §7 · pp. 31–33

7.2 The estimator for the lower-dimensional margins

  • The margin-wise estimation rates can be added, using the ANOVA decomposition, to obtain a rate for the whole tensor.The margin estimators use dimension-specific Vitali total-variation regularization.Source: §7.1 · p. 33, §7.2 · p. 34

8 Denoising the whole tensor

The section combines margin-wise results through the ANOVA decomposition to obtain bounds for denoising the whole tensor. It presents adaptive results for k = 1, 2, 3, 4 and a not-so-slow rate whose limiting component is the d-dimensional margin.

8 Denoising the whole tensor

  • The whole-tensor analysis combines the results for margins with the ANOVA decomposition.The section presents separate results for adaptive estimation and not-so-slow rates.Source: §8 · p. 35

8.1 Adaptivity of trend filtering

  • For k = 1, 2, 3, 4, the adaptive whole-tensor result is built from margin-wise bounds under hyperrectangular tessellation conditions.The theorem applies to arbitrary g and specifies tuning conditions.Source: §8.1 · p. 35
  • With regular-grid active sets and the stated tuning choices, the section gives a specialized rate from the adaptive result.The supplied passage does not state the rate expression.Source: §8.1 · p. 36

8.2 Not-so-slow rates for trend filtering

  • For the not-so-slow rate, the d-dimensional margin is limiting because the rate expression decreases with margin dimension.The whole-tensor analysis assumes n1 ≍ … ≍ nd ≍ n^1/d.Source: §8.2 · pp. 36–37

9 Conclusion

Structured penalties on tensor margins yield adaptive reconstruction at an almost parametric rate under the stated piecewise-polynomial condition. The appendix identifies its fast- and slow-rate oracle inequalities with adaptive and non-adaptive bounds.

9 Conclusion

  • With high probability, the normalized squared error is O(log^2 n/n) when the tensor is a product of polynomials on a constant number of hyperrectangles.The conclusion describes this as an almost parametric reconstruction rate.Source: §9 · p. 37
  • For k=1, 2, 3, or 4, the interpolating-tensor construction is not proved suitable for general k, leaving that extension open.The authors note that suitability can be checked by computer for each fixed finite k.Source: §9 · p. 37

A Oracle inequalities with fast and slow rates

  • The fast- and slow-rate oracle inequalities correspond, respectively, to the adaptive and non-adaptive bounds.The appendix relates these inequalities to earlier results, adapted to an enlarged active set.Source: A Oracle inequalities with fast and… · p. 41
  • Both oracle theorem statements allow arbitrary g and S, choose λ above a stated threshold, and give probability at least 1 − e^(−x) − e^(−t).The supplied theorem passages do not include the inequalities themselves.Source: A Oracle inequalities with fast and… · p. 41

B.1 Proof of Lemma 4.2

The proof excerpts use induction for Lemma 4.2 and develop antiprojection bounds in one and higher dimensions. They provide only fragments of the underlying calculations.

B.1 Proof of Lemma 4.2

  • The Lemma 4.2 proof proceeds by induction, with a base case at k=1 and a step from k−1 to k.The supplied excerpt does not state the lemma’s conclusion.Source: §B.1 · p. 41

C.1 Proof of Lemma 5.10

  • For bounding antiprojections, the proof uses dictionary Φ_k instead of the partially orthonormalized dictionary.The passage attributes this substitution to Lemma 28 of Ortelli and van de Geer [16].Source: §C.1 · p. 42

Bound on the antiprojections for general dimension d

Bound on the antiprojections for d = 1

  • In the one-dimensional antiprojection argument, a linear combination approximates the projection while a remainder upper-bounds the antiprojections.The proof says the same consideration applies in higher dimensions.Source: Bound on the antiprojections for d = 1 · pp. 42–43

C.3 Proof of Lemma 5.12

The proof constructs interpolating functions by matching derivatives across intervals, then uses properties of their discrete differences in an effective-sparsity bound.

C.3 Proof of Lemma 5.12

  • The proof checks that w satisfies the interpolating-tensor definition, with analogous expressions for q_tm=−1.The excerpt also considers q_tm=1 and indices in a rectangle R_m.Source: §C.3 · p. 45

C.4 Matching derivatives

  • Matching the first k−1 derivatives at interval junctions yields piecewise-constant kth derivatives, apart from the specified initial interval for ω.The construction chooses interval counts based on k and requires at least k points in each discrete counterpart interval.Source: §C.4 · pp. 45–46

C.5 Partial integration

  • The effective-sparsity calculation uses partial integration; a polynomial of degree k−1 has zero kth-order differences.The excerpt also states that (D^k p)_j = O(1/d^k).Source: §C.5 · pp. 46–47

C.6 Proof of Lemma 5.13

The proof bounds effective sparsity by splitting the interpolating tensor’s differences across hyperrectangles and accounting separately for their boundaries.

C.6 Proof of Lemma 5.13

  • The proof decouples partial integration over the whole interpolating tensor into kth-order differences on individual hyperrectangles.This removes dependence on the sign configuration when bounding effective sparsity.Source: §C.6 · p. 48
  • Boundary terms do not contribute to effective sparsity for k=1, but do contribute for k≥2.The passage states that the k≥2 boundary contribution must be upper-bounded.Source: §C.6 · p. 49

D Proofs of Section 6

For the inverse scaling factor with an enlarged mesh-grid active set, the proof decomposes dictionary atoms into components spanned by the grid and components contributing to the antiprojection.

Setting

  • The proof separates dictionary-atom components spanned by the enlarged mesh grid from those contributing to the antiprojection.It uses this decomposition to calculate the inverse scaling factor.Source: Setting · p. 49

The decomposition

  • The factors are decomposed into mutually orthogonal components, yielding a decomposition of a product of sums into a sum of products.The resulting dictionary-atom components are also stated to be mutually orthogonal.Source: The decomposition · p. 50

Partitioning the decomposition

  • The index set Σ consists of tuples with at most z entries no greater than z, for every z from 0 to d.In particular, Σ contains no tuple with an entry equal to 0.Source: Partitioning the decomposition · p. 50

Connecting the decomposition with the enlarged mesh grid

  • For tuples in Σ, products of component factors can be represented as linear combinations of dictionary atoms indexed by the enlarged mesh grid.These components are used to approximate projections of dictionary atoms onto the grid's span.Source: Connecting the decomposition with the… · p. 51

We need a claim

  • Increasing the final coordinate of a tuple in Σ by one preserves membership when that coordinate is at most d − 1.The proof establishes this by checking the defining count condition for Σ.Source: We need a claim · p. 51

Approximating the antiprojections

  • Mutual orthogonality and the preceding claim are used to approximate the antiprojections, with the remaining bound determined by contributions indexed by Σc.The proof identifies the largest contribution order among those indices and states that the resulting upper bound does not depend on the dictionary-atom indices.Source: Approximating the antiprojections · pp. 51–52
Loading 2101.10692v1…