{'fraction_non_alphanumeric': 0.05141657922350472, 'fraction_numerical': 0.014011480772791803, 'mean_word_length': 4.080589526497334, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
ROP inception: signal estimation with quadratic random sketching

Rank-one projections (ROP) of matrices and quadratic random sketching of signals support several data processing and machine learning methods, as well as recent imaging applications, such as phase retrieval or optical processing units. In this paper, we demonstrate how signal estimation can be operated directly through such quadratic sketches--equivalent to the ROPs of the"lifted signal"obtained as its outer product with itself--without explicitly reconstructing that signal. Our analysis relies on showing that, up to a minor debiasing trick, the ROP measurement operator satisfies a generalised sign product embedding (SPE) property. In a nutshell, the SPE shows that the scalar product of a signal sketch with the"sign"of the sketch of a given pattern approximates the square of the projection of that signal on this pattern. This thus amounts to an insertion (an"inception") of a ROP model inside a ROP sketch. The effectiveness of our approach is evaluated in several synthetic experiments.


Introduction
More and more algorithms in signal processing, optimisation, matrix algebra and machine learning rely on random projections. They are used to relax the computational burden of ever-growing data flows with data-agnostic dimensionality reduction procedures, such as linear random projections for data embedding or compressive sensing [2], while preserving specific information. Random projections are also used (in combination with nonlinear maps) to unfold (or embed) a dataset in larger dimensional feature spaces [10]. For example, this expanded domain can be more amenable to data separability or to clustering than the initial space, or endowed with specific kernels induced by the projection [14].
The estimation of specific properties (or functions) of signals is crucial to many data processing techniques, hence the ability to perform it in the feature ("projected") domain is of strong interest. For instance, one may be interested in processing video streams (e.g., for traffic monitoring, industrial quality control or video surveillance) to deduce localised data characteristics, i.e., restricted to a given area of the original field-of-view (e.g., for traffic density estimation or object detection [1]). Data processing tools based on random projection should thus comply with this goal, which can be challenging if the area-of-interest is unknown a priori, or subject to change.
In this work, we tackle the question of performing signal estimation-here restricted to the estimation of some linear function of a signal-from a projected data stream provided by quadratic random projections of signals (see Sec. 2). This specific data-agnostic projection is related to the sketching 1 technique of rank-one projections (ROP) [8,6]. Our work is motivated by a recent optical machine which performs ultra-rapid and low-power computations of such quadratic sketches [10]. However, with this technology, these computations are performed in a black-box manner, which prohibits us to explicitly access the random construction supporting the ROP model inside the localisation procedure-they are thus hidden to us (i.e., we do not have access to the adjoint ROP operator). Our main contribution amounts to showing theoretically that, up to some controlled distortion, signal estimation can be operated directly on quadratic signal sketches without reconstructing the signal (and hence avoiding often costly reconstruction methods [7,6,5,8]). More specifically, the square of this comparison-which is a ROP itself-can be approximated by projecting the sketched signal on the sign of the sketched pattern, i.e., summarising this last sketch to only the sign its components (see Sec. 3). We thus achieves a sort of inception of a ROP inside a ROP model. This result is thus similar to the techniques pursued in [3], where specific signal processing tasks are shown to be computable directly from compressive measurements. Our theoretical analysis is achieved from a generalisation of the sign product embedding (SPE) property, initially developed in one-bit compressive sensing [9,5].
To demonstrate the efficacy of our approach, we consider several synthetic signal estimation scenarios in Sec. 4. A first experiment quantifies the approximation error induced by our approach by considering a pattern that is orthogonal to the signal of interest. Next, we show how we can localise a rotating disk in one of the four quadrants of an image using only the image ROPs. Finally, we propose to classify MNIST handwritten digit images [4] directly in the DROP domain, with accuracy comparable to a direct processing of these images.

Sketching with hidden rank one projections
In this work, we consider the quadratic data sketching mechanism, which consists in taking a series of m quadratic measurements (a i x) 2 of a signal of interest x ∈ R n , with a set of m random vectors {a i } m i=1 ⊂ R n . The sketching operator A v applied to the vector x is thus defined as We assume that, while the operator A v can be computed, we cannot explicitly access to the random vectors {a i } m i=1 . This restriction is indeed required by a recent optical technology, named Optical Processing Unit (OPU) [10]. An OPU allows us to compute all the components of A v (x) in a reproducible way using the physical properties of multiple scattering of coherent light in random media, which is thus extremely fast and power-efficient (even if m n). In this context, the vectors {a i } m i=1 are fixed, but hidden to us. Moreover, following the observations made in [10], we assume that each random vector a i is i.i.d. as a Gaussian random vector 2 a ∼ N (0, I n ), with identity covariance I n .
As observed in the context of phase retrieval [7], the operator A v amounts to a rank-one projection of the lifted signal, i.e., the rank-one matrix X = xx ∈ R n×n , onto the rank-one random matrices where ·, · is the Frobenius inner product [8,6]. We thus use "quadratic sketch" and "ROP measurements" interchangeably. As the ROP operator is biased-i.e., given a signal x, there is no constant An OPU can trivially implement this operation by applying finite pixel differences in its focal plane. It can be shown that 1 Lemma 4]. While the approximation 1 4m B(x) 2 ≈ x 4 is hard to achieve at reasonable values of m-B respects the restricted isometry property (RIP) in only a few restrictive settings [8,6]-we leverage below another useful property of B.

Signal estimation in the DROP domain
Our objective is to show that we can do (approximate) signal estimation-when this estimation amounts to estimating a linear function of the signal-directly from random quadratic signal sketches, and thus without knowing the observed signal. This is possible by demonstrating that the DROP operator respects, with high probability, the (local) sign product embedding (SPE) property [9], whose proof is postponed to App. A. This SPE is here instantiated on a signal space S consisting of k sparse signals of Σ k := {v ∈ R n : |supp(v)| ≤ k}. However, by rotational symmetry of the Gaussian distribution, the proposition below is also valid for sets of k sparse signals in an orthonormal basis Ψ ∈ R n×n (such as the wavelet or Fourier bases).
Proposition 1. Given a fixed unit vector u ∈ R n , κ = π/4, and a distortion 0 then, with probability exceeding with sign the sign operator applied componentwise on vectors.
This proposition states that, provided that m is large compared to the dimension of the signal space S (here S = Σ k and we thus need m = Ω(δ −2 k) up to log factors), for any vector x ∈ S, projecting its sketch B(x) on sign(B(u)) ∈ {±1} m is a proxy for u, x 2 -a ROP of xx by uu . The spirit of this result is thus similar to the approach of [3] in linear compressive sensing [3], where a set of signal processing techniques (including signal estimation) are proved to be applicable in the compressed signal measurements. Let us emphasise that the error of the approximation (4) is bounded by δ x 2 , that is O( k/m x 2 ) (up to log factors) by saturating (3). Therefore, the equation (4) is useful only if u, x/ x 2 is sufficiently large compared to δ. Incidentally, this allows us to estimate δ as a function of m by taking a vector u orthogonal to x (see Sec. 4). Notice that, by a simple union bound argument, Eq. 4 in Prop. 1 can be shown to hold with the same probability bound for all u in a finite set of S unit vectors provided m ≥ Cδ −2 (k log( n kδ ) + log S) (see Cor. 3 in App. A).

Experiments
This section contains three experiments demonstrating how one can directly carry out signal estimation in the range of the DROP operator. Our first experiment aims at measuring the approximation error (δ) in (4). For this purpose, we took two unit vectors x, u ∈ R n picked uniformly at random on the sphere S n−1 with the additional constraint that u must be orthogonal to x. In this case, the term u, x 2 vanishes in (4) and one can estimate δ by Monte Carlo simulations over several trials of κ m sign(B(u)), B(x) . We show in Fig. 1(top-left) the estimated δ over 100 trials (average and maximum value) for n = 1000 and varying ratio m/n ∈ [0. 1,10]. This estimation confirms that δ decays as O(m −1/2 ) when m increases. Moreover, on average, δ 0.1 as soon as m/n > 0.2.
As a second experiment, we test the possibility to perform localised detection in a simple synthetic video; a sequence of 24 images {x t } 23 t=0 of size 128 × 128 (n = 16 384) representing a white disk rotating on a black (zero) background (see Fig. 1(top-right)). Our objective is to detect the passage of the disk in each of the four image quadrants by only processing the DROP measurements {B(x t )} 23 t=0 ⊂ R m . We have thus created 4 normalised patterns {u j } 4 j=1 , with u j being constant in the j-th quadrant and 0 outside, for each 1 ≤ j ≤ 4. We show in Fig. 1(bottom) the time evolution of q est j (t) := κ m sign(B(u j )), B(x t ) (continuous curves) for m/n = 0.5 in comparison with the quadrant occupancy functions q j (t) := u j , x t 2 (dashed lines). The colour coding is given in the legend. We observe that each curves q est j (t) provides a fair estimation of q j (t). Moreover, the amplitude of each curve q est j (t) reduces when the disk is not in the associated quadrant. A rough detection of the quadrant occupancy could thus be established by appropriately thresholding each time signal q est j (t). As final illustration, we perform a toy example (naive) classification of images taken in the labelled MNIST dataset X := {(x k , t k )} N =70 000 k=1 ⊂ R 28×28 × {0, . . . , 9} [4] (with normalisation x k = 1). We want to compare the classification performed in the direct, pixel domain, to the one operated in the sketched domain. We start by randomly splitting X into a training X tr and a test set X te according to a split of 60 000 and 10 000 images, respectively. From X tr we compute the 10 centroids {c j } 9 j=0 ⊂ R 28×28 of each class of digits and we define 10 vectors u j = c j / c j . In the direct domain, the estimated label of an image x k is then defined ast k := arg max j u j , x k 2 . In the sketched domain, the label estimate of a test image x k is computed ast sk k := arg max j κ m sign(B(u j )), B(x k ) , which should be close tot k according to Prop. 1. We reach the following average testing accuracy (100 trials, ± standard deviation in %) for both the direct and the sketched classifications: These results confirm that, up to some distortion, one can apply this naive classification procedure directly in the DROP measurements of the dataset. As predicted by our analysis, this approximation improves when m increases.
To prospectively question the possibility to reach better classification accuracy in the DROP domain, we consider the dataset , and compute the centroids {c B j } 9 j=0 ⊂ R m in the training split of X B . We then compare two possible classification methods. The first proceeds as a direct classification in the DROP domain, i.e., we compute the label estimatê t B k := arg max j c B j , B(x k ) . The second approach assumes that, for each centroid, there exists a vector v j such that c B j ≈ B(v j ). Under this assumption, we rather estimate our label by applying a sign operation to each c B j -which is more aligned to Prop. 1-and we computê t B,sign k := arg max j sign(c B j ), B(x k ) . We reach the following average testing accuracy for the two approaches (for m = 800, 500 trials, ± standard deviation in %): Keeping only the sign of the estimated centroids provides better testing accuracy than the unsigned method. In fact, the signed approach outperforms the testing accuracy of the direct approach by about 3%.

Conclusion and perspectives
Our developments have shown that signal estimation is possible by directly processing the quadratic measurements of a signal. We achieved this by showing that such ROP measurements satisfy the sign product embedding with high probability provided m is sufficiently large compared to the signal space dimension. Our theoretical results were backed up by several synthetic signal estimation and classification experiments. In future works, we plan to reproduce this experiment on an actual OPU to further reduce the computational cost of the procedure, by also leveraging the one-bit nature of the signed sketches.

A Proofs
In this appendix, we start by providing a proof of the isotropy of the DROP operator B. A more general proof is provided in [8,Lemma 4] (where B is extended to the mapping of matrices of any rank and for sub-gaussian random vectors a i ), but we find useful to provide below a short alternate proof for the sake of self-containedness.
Proposition 2 (DROP isotropy). Given x ∈ R n , we have Proof. By rotational symmetry of the Gaussian distribution and by homogeneity of (5) in x 4 , it is enough to prove Prop. 2 for x = e 1 := (1, 0, . . . , 0) . In this case, for two independent random vectors a, b ∼ N (0, I n ), we easily show that 1 We now prove the central result of this work, Prop. 1, which is reproduced below for convenience.
Proof. Let us first show that the expectation of κ m sign(B(u)), B(x) is actually equal to u, x 2 . By rotational symmetry of the Gaussian distribution and homogeneity of this expectation in x 2 , it is enough to prove it for u = e 1 and x = ce 1 + se 2 , with c = cos θ, s = sin θ, and θ the angle between x and u.
In this case, for two independent random vectors a, b ∼ N (0, I n ), we easily show that and s i (u) = sign[(a 2i u) 2 −(a 2i+1 u) 2 ]. The random variables Z i are all i.i.d. and sub-exponential since their sub-exponential norm is bounded as see [11,Def. 5.13 & Lemma 5.14]. Therefore, from [11,Cor. 5.17], for any δ ≥ 0, we get the concentration result P |S| ≥ δm ≤ 2 exp(−c min(δ 2 , δ)m), or Finally, we extend the previous concentration result for a fixed unit vector u and for all vectors of Σ k . By the same homogeneity argument, it is enough to prove the final claim of Prop. 1 for all unit k-sparse signals x of Σ k ∩ S n−1 .
Let us observe that, for all 1 ≤ i ≤ m, and X = xx . Moreover, the lifted matrix X has rank one, unit Frobenius norm and is sparse along its rows and columns, or bi-sparse [13]. Therefore, given a radius > 0 to be fixed momentarily, there exists a -covering G ⊂ G of the lifted set G := {xx : x ∈ Σ k ∩ S n−1 } such that for any X ∈ G there is a X ∈ G with same row and column supports and X − X ≤ . Moreover, its cardinality |G | does not exceed n k (9/ ) 2k+1 [12, Lemma 3.1], which is crudely bounded by ( cn k ) 2k+1 . Fixingū := sign(B(u)), since by a standard union bound argument applied to (6), we thus see that, with probability exceeding 1 − 2|G | exp(−c min(δ 2 , δ)m), we have for all X ∈ G | κ m ū, d i X s i − u X u| ≤ δ.
The rest of the proof assumes that this event holds. Let us define the n × n matrix We then have for all X ∈ G, κ m ū, d i Xs i − u Xu = Q, X .
The following corollary extends Prop. 4 to the case where u belongs to a finite set of unit vectors.
The proof of this corollary consists in bounding the failure of (7) using Prop. 1 and a simple union bound argument.