Source-linked AI summary
Random Projections through multiple optical scattering: Approximating kernels at the speed of light
Alaa Saade, Francesco Caltagirone, Igor Carron, Laurent Daudet, Angélique Drémeau, Sylvain Gigan, Florent Krzakala
TL;DR
Kernel methods can require storing large kernel matrices, while random-feature methods still incur the cost of generating and storing projection matrices. The paper uses coherent multiple scattering in an optical device to produce random projections, and reports that optical and synthetic projection classification results agree closely on MNIST.
Problem
Kernel machines can require storing all pairwise kernel values, and explicit random-feature approaches can make generating and storing large projection matrices a computational bottleneck.
Source: §I · p. 1Method
The authors use coherent light scattering in a random medium to produce random projections whose mapped-feature inner products approximate an elliptic kernel.
Source: §I · p. 1, C. Random complex projections and the… · p. 3, A. Principle of optical analog random… · p. 4Results
Optical and synthetic random-projection classification curves agree remarkably well; the elliptic-kernel MNIST error was 1.31%.
Source: A. Kernel classification · p. 2, §IV · p. 5Takeaways & Limitations
The device obtains high-dimensional projections almost instantaneously and is presented as a proof of concept for optical co-processors complementing silicon chips.
Source: §V · p. 5At N ≳2000, optical results depart from synthetic ones; the authors suspect residual output-pixel correlations despite finding robustness to experimental noise.
Source: §IV · p. 5
Abstract
from arXiv · showhide
Random projections have proven extremely useful in many signal processing and machine learning applications. However, they often require either to store a very large random matrix, or to use a different, structured matrix to reduce the computational and memory costs. Here, we overcome this difficulty by proposing an analog, optical device, that performs the random projections literally at the speed of light without having to store any matrix in memory. This is achieved using the physical properties of multiple coherent scattering of coherent light in random media. We use this device on a simple task of classification with a kernel machine, and we show that, on the MNIST database, the experimental results closely match the theoretical performance of the corresponding kernel. This framework can help make kernel methods practical for applications that have large training sets and/or require real-time prediction. We discuss possible extensions of the method in terms of a class of kernels, speed, memory consumption and different problems.
I. INTRODUCTION
Random projections support dimensionality reduction and nonlinear feature embeddings, but kernel machines can require a kernel matrix that does not scale to large datasets. The paper motivates optical hardware as a way to bypass the computational bottleneck of generating random projections.
I. INTRODUCTION
- Random projections can reduce feature dimensions while approximately preserving pairwise distances, and can also support sparse-signal reconstruction.The passage associates the first use with the Johnson-Lindenstrauss lemma and the second with compressed sensing.Source: §I · p. 1
- Kernel machines avoid explicitly mapping data by using pairwise kernel inner products, but storing all pair values typically does not scale to large datasets.The kernel may correspond to an embedding with a possibly infinite dimension.Source: §I · p. 1
- Explicit random-feature methods make large-scale learning tractable, but generating, storing, and multiplying by a large random matrix has become a major bottleneck.The cited passage describes mappings whose inner products approximately reproduce kernel evaluations.Source: §I · p. 1
- The proposed optical hardware supplies random projections without lengthy calibration, relying on statistical properties and yielding results reported as consistent with simulations despite experimental noise.The device is presented as a generic digital data pre-processor for later uses.Source: §I · p. 1
II. RANDOM PROJECTIONS AND KERNEL MACHINE LEARNING
The section formulates supervised ridge regression using training and test data, then expresses prediction through the learned coefficients. Its classification output is the label with the largest predicted value.
II. RANDOM PROJECTIONS AND KERNEL MACHINE LEARNING
- The training set is represented by labeled feature vectors in U and label matrix Y, while ˜U contains unlabeled test samples whose labels are estimated.The passage defines n training samples, p features, q labels, and ˜n test samples.Source: §II · p. 2
- The ridge solution uses (U^T U + γI_p)^−1U^T Y, equivalently U^T(UU^T + γI_n)^−1Y.The regularization parameter γ controls the trade-off between estimation error and regularization.Source: §II · p. 2
- Test labels are predicted from the test features and learned coefficients, and classification selects the label with the largest predicted value.The passage also notes that the prediction depends only on data-point inner products.Source: §II · p. 2
A. Kernel classification
Kernel ridge regression replaces feature-space inner products with kernel evaluations, avoiding an explicit feature mapping. On MNIST, the elliptic kernel substantially outperforms linear ridge regression, while the figure shows random-projection error approaching the kernel result as dimension grows.
A. Kernel classification
- Kernel ridge regression replaces feature-space inner products with kernel evaluations, so the explicit feature mapping is unnecessary.The method uses kernel matrices for training-pair and test-to-training evaluations.Source: A. Kernel classification · p. 2
- The elliptic kernel uses complete elliptic integrals and the angle between inputs, and its value behaves like a bell curve as a function of that angle.The passage describes it as quantifying similarity between inputs.Source: A. Kernel classification · p. 2
- 1.31% MNIST classification error with the elliptic kernel compares with 12% for linear ridge regression.The experiment uses 60,000 training digits and 10,000 test digits.Source: A. Kernel classification · p. 2, Figure 1 · p. 3
- As feature dimension N increases, synthetic-projection error approaches the 1.31% true-elliptic-kernel asymptote, while optical results closely follow synthetic results but tend to deviate.Source: Figure 1 · p. 3
B. Random projections
Random projections approximate a nonlinear feature map using a random linear transform, bias, and nonlinearity. This can approximate kernel ridge regression with a smaller matrix inversion, and the reported synthetic MNIST experiment reaches approximately 2% error using 10,000 projections.
B. Random projections
- The mapped features are X_i,j = φ((WU_i)_j + b_j), with random linear projection W, nonlinearity φ, and bias b.The mapping follows prior work cited as.Source: B. Random projections · p. 3
- Approximately 2% error is obtained on MNIST with N=10,000 random projections, inverting a 10,000² matrix instead of a 60,000² matrix.The smaller inversion removes dependence on n² in this formulation.Source: B. Random projections · p. 3
C. Random complex projections and the elliptic kernel
As the number of random projections grows, their inner products converge to the elliptic kernel, and MNIST classification error approaches the kernel’s 1.31% error. The finite-projection corrections are empirically fitted by a power law in N^-2/3.
C. Random complex projections and the elliptic kernel
- As N grows, classification error using synthetic random projections approaches the true elliptic-kernel value of 1.31% on MNIST.The limiting kernel for the experiment’s projection choices is the elliptic kernel.Source: C. Random complex projections and the… · p. 3
- In the large-N limit, inner products between projected data points converge to a kernel function depending only on the original inputs.For the experiment’s choices of W and φ, that limiting function is the elliptic kernel.Source: C. Random complex projections and the… · p. 3
- Finite-N corrections to the asymptotic classification error are empirically fitted by a power law in N^-2/3.The convergence is illustrated using classification error on MNIST as the number of projections increases.Source: C. Random complex projections and the… · p. 3
III. EXPERIMENTAL APPARATUS
The apparatus is introduced as a way to make the projection procedure instantaneous, avoiding storage and multiplication by a potentially huge random matrix and application of the modulus function. It illuminates a random medium with encoded light and measures the transmitted light with a camera.
III. EXPERIMENTAL APPARATUS
- The apparatus is intended to make the projection procedure instantaneous, avoiding a potentially huge random matrix and the modulus operation.The preceding approach still requires storing and multiplying by the matrix.Source: §III · p. 4
- A DMD spatially encodes information on a 532 nm laser beam, which a lens focuses onto a thick TiO2 nanoparticle layer.The layer consists of white-paint pigments deposited on a microscope glass slide.Source: Figure 2 · p. 4
- After transmission through the random medium, light passes through a polarizer and is measured by a monochrome CCD camera.A second lens collects the transmitted light.Source: Figure 2 · p. 4
A. Principle of optical analog random projections
The method uses complex scattering in heterogeneous materials to mix input-light information into a measurable output. With coherent light, a stable medium’s scattering supports random projections without determining its transmission matrix.
A. Principle of optical analog random projections
- The term “random medium” describes scattering that is effectively unpredictable, although the process is linear, deterministic, and reproducible.The materials discussed include paper, paint, and other white translucent materials.Source: A. Principle of optical analog random… · p. 4
- Light propagation through the material entails frequent scattering, with a transport mean free path typically a few micrometers and tens of thousands of steps before exit.For the described layer, the light exits after a few picoseconds.Source: A. Principle of optical analog random… · p. 4
- Coherent light produces a speckle interference pattern that depends on both the heterogeneous material and the input-light shape.The scattering process is modeled as y = Hx, with H close to a Gaussian i.i.d. matrix.Source: A. Principle of optical analog random… · p. 4
- For a stable medium such as paint, the transmission matrix H is stable, so the medium can provide random projections without determining H.The output intensity |y|^2 is measured after interrogating the medium with input illuminations.Source: A. Principle of optical analog random… · p. 4
B. Encoding the data on the DMD
The DMD represents image gray levels spatially by assigning each pixel a 4 × 4 mirror array, allowing 17 levels. The encoded binary image is projected onto the DMD, and the measured output is downsampled to reduce correlations between neighboring pixels.
B. Encoding the data on the DMD
- Spatial encoding represents each pixel’s gray level by the number of lit mirrors in a 4 × 4 array, yielding 17 gray levels.The DMD mirrors are binary; encoding gray levels in time would reduce processing frequency.Source: B. Encoding the data on the DMD · p. 5
- Each MNIST image is quantized to levels 0–16, encoded as 4 × 4 mirror arrays, bordered with zeros, and rescaled to the 1920 × 1080 DMD.The procedure can generalize to numerical-vector data, and larger mirror arrays could encode more gray levels.Source: B. Encoding the data on the DMD · p. 5
- The camera snapshot is reduced from a 400²-pixel area to 100² pixels by averaging each 4² patch to reduce neighboring-pixel correlations.The resulting snapshot is used as the random projection.Source: B. Encoding the data on the DMD · p. 5
IV. RESULTS
Experimental and synthetic random projections produce remarkably similar classification curves. At large projection counts, residual output-pixel correlations are suspected of causing a divergence.
IV. RESULTS
- The experimental and synthetic random-projection classification curves agree remarkably well, validating the analog projection procedure.The comparison is summarized in Fig. 1.Source: §IV · p. 5
- For N ≳2000, the optical experiment deviates from the synthetic result, despite classification robustness to large added synthetic noise.The authors suspect residual output-pixel correlations and suggest matching CCD pixel size to speckle grains or tuning medium thickness to increase independent modes.Source: §IV · p. 5
V. CONCLUSION AND PERSPECTIVES
The optical device produces large-dimensional random projections almost instantaneously, with speed limited by light modulation and measurement. The authors present it as a proof of concept for optical co-processors and outline extensions to larger signals and broader kernel processing.
V. CONCLUSION AND PERSPECTIVES
- The device produces 10^4–10^6-dimensional projections almost instantaneously, with speed limited by input light modulation and scattered-light measurement.The authors note off-the-shelf DMDs can handle millions of pixels at 20 kHz or above.Source: §V · p. 5
- An interferometric arm could enable linear projections, while FPGAs could apply nonlinear functions to widen the range of approximated kernels.Several DMDs could also be combined to process larger signals.Source: §V · p. 5
- The experiment is a proof of concept for analog optical co-processors that could complement silicon chips for very large datasets, with potential throughput and energy benefits.Source: §V · p. 5