QuantumCore

Hands-on lab · 1 step

The RBF Gram matrix

Implement the Gram matrix Kij=k(xi,xj)=e−γ∥xi−xj∥2K_{ij}=k(x_i,x_j)=e^{-\gamma\lVert x_i-x_j\rVert^2} of the Gaussian (RBF) kernel, the matrix that the SVM dual and every kernel method consume. The grader checks your values on a visible three-point example and on three hidden sets of 2020 random points in [−2,2]2[-2,2]^2 (γ=0.5,1,2\gamma=0.5,1,2), and verifies the two structural properties that every valid Gram matrix has: symmetry and positive semidefiniteness.

0/1 step passedBest score 0/100

Step 1: Compute the RBF Gram matrix

Write the TypeScript function rbfGram with signature

rbfGram(X,γ) ⟼ K∈Rm×m,Kij=exp⁡ ⁣(−γ ∥xi−xj∥2)=exp⁡ ⁣(−γ∑t=1d(xi,t−xj,t)2),\texttt{rbfGram}(X,\gamma)\ \longmapsto\ K\in\mathbb R^{m\times m},\qquad K_{ij}=\exp\!\big(-\gamma\,\lVert x_i-x_j\rVert^2\big)=\exp\!\Big(-\gamma\sum_{t=1}^{d}(x_{i,t}-x_{j,t})^2\Big),

where row ii of X is the data point xi∈Rdx_i\in\mathbb R^d and gamma is γ>0\gamma>0. Return a plain array of mm rows of mm numbers each. The norm is squared: no square root is taken.

Visible test three-points: X={(0,0),(1,0),(0,2)}X=\{(0,0),(1,0),(0,2)\} and γ=0.5\gamma=0.5. The squared distances are ∥x0−x1∥2=1\lVert x_0-x_1\rVert^2=1, ∥x0−x2∥2=4\lVert x_0-x_2\rVert^2=4 and ∥x1−x2∥2=1+4=5\lVert x_1-x_2\rVert^2=1+4=5, so

K=(1e−0.5e−2e−0.51e−2.5e−2e−2.51)≈(10.60653065970.13533528320.606530659710.08208499860.13533528320.08208499861),K=\begin{pmatrix}1&e^{-0.5}&e^{-2}\\ e^{-0.5}&1&e^{-2.5}\\ e^{-2}&e^{-2.5}&1\end{pmatrix}\approx\begin{pmatrix}1&0.6065306597&0.1353352832\\0.6065306597&1&0.0820849986\\0.1353352832&0.0820849986&1\end{pmatrix},

compared entrywise with absolute tolerance 10−910^{-9}.

Hidden tests (arguments are sent to your browser, expected values are not): three data sets of m=20m=20 points in [−2,2]2[-2,2]^2 with γ=0.5\gamma=0.5, 11 and 22. For each set: (values) every entry within 10−910^{-9} of the reference matrix; (symmetric) max⁡ij∣Kij−Kji∣≤10−12\max_{ij}\lvert K_{ij}-K_{ji}\rvert\le10^{-12}; (psd) the smallest eigenvalue of KK, computed by the engine's Hermitian eigensolver, is at least −10−10-10^{-10}.

Use Math.exp; do not import anything.

TypeScript: export rbfGram · 10 tests · imports: quantumcore, quantumcore/qml
Run the tests first; the results of your latest run are submitted.