text:
Landon Donovan – USMNT
April 2, 2008 by US Soccer Players
Pro Team: Los Angeles Galaxy
Caps: 157
Landon Donovan spent over a decade earning his reputation as one of the best players in USMNT history. lightning quick on the ball and possesses a lethal touch in front of goal. His vision and skill make him one of the most highly-touted players ever to come out of the USMNT youth programs. He is already the all-time scoring leader for the USMNT, winning the Honda Player of the Year award a record six times. He was also the Honda Player of the Decade for the 2000's.
Landon Donovan has had more success than any other US youth player at the U-17, U-20, and Olympic levels, and he earned a spot with the USMNT in 2002 World Cup qualifying. In 2002, Donovan cemented himself in the US line-up with six goals in 19 games, including two in the World Cup against Poland and Mexico.
Donovan led the team in appearances and points during 2006 World Cup qualifying, playing in 16 of 18 matches while scoring six goals and registering six assists for 18 points. He recorded a point in 12 of 16 qualifying appearances in the 2006 campaign, an amazing statistic. His three assists in 2006 moved him into first place on the USA's all-time list with 23, then in January 2008 he scored against Sweden to move ahead of Eric Wynalda to become the all-time leader on the US goal scoring list with 35. Landon Donovan is the youngest player in USMNT history to reach 50 caps.
Donovan's 2010 World Cup added another chapter to his already lengthy resume. He started all four games, scoring against Slovenia, Algeria, and Ghana as the US advanced to the knockout round. He was named US Soccer Male Athlete of the Year for the fourth time in December, 2010.
Donovan announced during the 2014 MLS season that he planned to retire from professional soccer. He set the all-time MLS assist record in October. In September, 2016 he announced his return to MLS, rejoining the Galaxy for the rest of the season. In January, 2018 Donovan made a surprise return to pro soccer, signing with Leon in Liga MX and playing during the Clausura season.
"I don't think about the past too often. There's not a lot to gain from that. I think we learned our lesson from that game. We still came away with our heads held high and, most importantly, we now have the confidence that we can beat any team in the world on a given day." from 10 Questions With Landon Donovan
Landon Donovan USMNT Highlights
2014: Started against Korea on Feb 1. Subbed on against Mexico on Apr 2. Named to the provisional World Cup roster. Played his farewell game with the USMNT against Ecuador on Oct 10. Started and captained the USMNT.
2013: Started against Guatemala on Jul 5 and converted a penalty for the 50th goal of his international career before scoring his 51st goal. Started against Belize on Jul 9, converting a penalty for the 6th USA goal. Converted a first-half penalty against Cuba on Jul 13. Started against Costa Rica on Jul 16. Started in the Gold Cup quarterfinal against El Salvador on Jul 21 and scored the fourth goal. Started against Honduras in the semifinal on Jul 24 and scored two goals. Started the final against Panama on Jul 28. Started against Costa Rica on Sep 6. Started against Mexico on Sep 10 and scored. Started against Jamaica on October 11.
2012: Started against Scotland on May 26th and scored a hat-trick.
2011: Started against Argentina on March 26th. Captained the US against Paraguay on March 29th. Scoring in the Gold Cup final against Mexico on June 25th.
2010: Played against Turkey in the Sendoff Series. Named to the 2010 World Cup roster. Had an outstanding World Cup, scoring in three of the four games including the stoppage time winner against Algeria to advance the USA to the knockout round. Won US Soccer's Athlete of the Year award.
2009: Regular starter for the United States, had three assists in the 2-0 win over Trinidad & Tobago on April 1st. Converted a penalty against Costa Rica on June 3rd and another against Honduras three days later. Quality showing in the Confederations Cup, including a goal in the final against Brazil. Score the goal that ended up clinching qualifying for the USA against Honduras. Named the Honda Player of the Year and Player of the Decade.
2008: Set the National Team scoring record with his 35th goal, a penalty against Sweden on January 19 in Carson, Ca. Set up first goal for Oguchi Onyewu with an overhead cross during 2-2 exhibition tie against Mexico in Houston.
2007: Scored counter-attacking game-clincher against Mexico in 2-0 February exhibition win, then a stunning hat-trick against Ecuador the following month. Played in all six Gold Cup games (five starts), scoring four goals as US took trophy. Leveled Eric Wynalda as all-time US leading goal scorer. Nine goals and four assists in 12 games (11 starts) over the course of the year.
2006: Led the US in appearances by playing in 11 out of 13 games, including all three Group E matches in the 2006 World Cup. Registered three assists.
2005: One of the stars for the US during final round qualifying, he finished with three goals and four assists in eight matches. Scored a pair in the 3-0 win against Costa Rica on June 4 in Salt Lake, then added the middle goal in the 3-0 win against Panama four days later. Scored three goals in the USA's championship run in the 2005 Gold Cup, including a double off the bench on July 7 against Cuba. One of three US players named to the All-Tournament Team.
2004: Became first player to win US Soccer Male Athlete of the Year and Youth Male Athlete of the Year award (2000). Ended the year with the most minutes played (1,243) and games started (14) and tied for the lead in goals scored (5). Named man of the match four times.
2003: Became first player to win Honda U.S. Player of the Year in consecutive years. Led the team in scoring with seven goals and five assists. Tied a US record with four goals in the Gold Cup quarterfinal win over Cuba.
2002: Won Honda U.S. Player of the Year. Started all five games for the US in World Cup, scoring once each against Poland and Mexico, and led the team in shots on goal (7). Started all five games for US in winning the 2002 Gold Cup, and was named to tournament Best XI.
2001: Drew the penalty that led to the game-winning goal against Jamaica that clinched qualification for the 2002 World Cup. Earned his first of three World Cup qualifying starts in the 3-2 loss to Honduras on September 1, 2001, and also appeared as a substitute against Costa Rica on September. Started all four games at the FIFA World Youth Championship in Argentina, leading the US to the second round.
2000: Became the sixth player since 1985 to score a goal in his first appearance with the full US team when he tallied in the 2-0 win over Mexico in Los Angeles on October 25. Named US Soccer Youth Male Athlete of the Year.
Played in four games at the 2000 Olympics, scoring a goal against Kuwait. Scored two goals with the U-23s in the crucial 4-0 win over Guatemala to earn Olympics berth. Scored nine goals and one assist in 15 games with the U-20 national team, including four goals in eight internationals.
1999: Helped the U-23 team to a bronze medal at the 1999 Pan American Games, appearing in all six matches and starting four.
1999: Scored three goals in the 1999 U-17 World Championship in New Zealand and earned the Golden Ball as the tournament's most valuable player after leading the USA to a fourth-place finish.
Landon Donovan Professional Highlights
2018: Signed a one year contract with Liga MX club Leon in January. LEft the club following the Clausura season.
2016: Returned to the Galaxy in September and made the playoffs. Retired again at the end of the season.
2014: Won the MLS Cup in his final season with the Galaxy. Announced his retirement following the season.
2013: A regular in a Galaxy side that finished third in the Western Conference.
2012: Donovan returned to Everton for a two month loan from January to February. Won a second-consecutive MLS Cup with the Galaxy.
2011: Won MLS Cup, scoring the game-winner in the final and being named MLS Cup MVP.
2010: Loaned to Everton where he had a strong run of form before returning to the Galaxy.
2009: Loaned to Bayern Munich in the German Bundesliga, Donovan played in six games before returning to the LA Galaxy. Part of an LA squad that lost the MLS Cup final.
2008: Scoring leader for Major League Soccer with 20 goals and a strong MVP candidate with a Galaxy team that missed the playoffs.
2007: Despite the LA Galaxy's disappointing season, he still lead the team with eight goals and 13 assists.
2006: Tallied a career-high 12 goals to go with and eight assists, despite missing eight games while with the US National Team at the World Cup in Germany ... Was named to the MLS All-Star Team for the sixth straight season.
2005: Returned to Bayer Leverkusen in January where he saw limited action (9 games). Decided to return to MLS and make it his permanent home, signing with the LA Galaxy in late March.
2004: Posted six goals and ten assists. Voted an Earthquakes All-Star for the fourth straight year.
2003: Named MVP after scoring two goals to lead Earthquakes to MLS Cup title. Led Earthquakes in scoring with 12 goals and six assists.
2002: Reached agreement with Bayer Leverkusen to extend MLS loan deal for another two years. Scored seven goals and three assists in 20 games played
2001: Registered seven goals and 10 assists for the San Jose Earthquakes, leading them to their first MLS Cup title. Scored four goals at the 2001 MLS All-Star game in San Jose. Moved from Bayer Leverkusen to San Jose in March 2001 after the two sides worked out a co-sharing agreement.
2000: Played with Leverkusen's reserves alongside fellow US National Team member John Thorrington.
1999: Signed at the age of 16 with German Bundesliga side Bayer Leverkusen.
Youth: A 1999 Parade High School All-American, Landon starred at Redlands East Valley High School, scoring 16 goals in 1998 before joining the US Under-17 team in residency camp in Bradenton, Fla. Credits US U-17 head coach John Ellinger and California head coach Clint Greenwood for making him the player he is today: "Clint taught me almost every technical skill I have today and John turned me into a professional."
Like 1 Google +1 Retweet
Filed Under: Players Tagged With: bio, us soccer
Seattle in the Champions League
As the MLS Cup winners, the Seattle Sounders are the latest club to enter the Champions League while trying to balance their title defense.

redpajama_set_name: RedPajamaCommonCrawl


text:
\section{Introduction}\label{sec:intro}
The practical applications of traditional entropy measures e.g. Shannon's entropy \cite{shannon1948mathematical} and R\'enyi's entropy \cite{renyi1961measures} have long been hindered by their heavy reliance on the underlying data distributions, which are extremely hard to estimate or even intractable in high-dimensional spaces \cite{fan2006statistical}. Alternatively, the matrix-based R\'enyi's entropy proposed by \citep{giraldo2014measures} treats the entire eigenspectrum of a normalized kernel matrix as a probability distribution, thus allows direct quantification from given data samples by projecting them in reproducing kernel Hilbert spaces (RKHS) without the exhausting density estimation. This intriguing property makes matrix-based R\'enyi's entropy and its multivariate extensions \cite{yu2019multivariate} successfully applied in various data science applications, ranging from classical dimensionality reduction and feature selection \cite{brockmeier2017quantifying, alvarez2017kernel} problems to advanced deep learning problems such as network pruning \cite{sarvani2021hrel} and knowledge distillation \cite{miles2021information}.

Despite the empirical success of matrix-based R\'enyi's entropy, it has been shown to be not robust against noises in the data \cite{yu2019multivariate}, because it cannot distinguish them from linear combinations of informative features in high-dimensional scenarios. Moreover, the exact calculation requires $\mathcal{O}(n^3)$ time complexity with traditional eigenvalue decomposition techniques e.g. CUR decomposition and QR factorization \cite{mahoney2009cur, watkins2008qr}, greatly hampering its application in large scale tasks due to the unacceptable computational cost.

Inspired by the success of min-entropy which uses the largest outcome solely as a measure of information \cite{wan2018min, konig2009operational}, we seek for a robust information quantity by utilizing low-rank representations of kernel matrices. Our new definition, termed low-rank matrix-based R\'enyi's entropy (abbreviated as low-rank R\'enyi's entropy), fulfills the entire set of axioms provided by R\'enyi \cite{renyi1961measures} that a function must satisfy to be considered a measure of information. Compared to the original matrix-based R\'enyi's entropy, our low-rank variant is more sensitive to informative perturbations caused by variation of the underlying probability distribution, while being more robust to uninformative ones caused by noises in the data samples. Moreover, our low-rank R\'enyi's entropy can be efficiently approximated by random projection and Lanczos iteration techniques, achieving substantially lower time complexity than the trivial eigenvalue decomposition approach. We theoretically analyze the quality of approximation results, and conduct large-scale experiments to evaluate the effectiveness of low-rank R\'enyi's entropy as well as the approximation algorithms. The main contributions of this work are summarized as follows:
\begin{itemize}
    \item We extend Giraldo et al.'s definition and show that a measure of entropy can be built upon the low-rank representation of the kernel matrix. Our low-rank definition can be naturally extended to measure the interactions between multiple random variables, including joint entropy, conditional entropy, and mutual information.

    \item Theoretically, we show that low-rank R\'enyi's entropy is more insensitive to random perturbations of the data samples under mild assumptions. We also give empirical examples of low-rank R\'enyi's entropy achieving higher discriminability for different eigenspectrum distributions through a proper choice of the hyper-parameter $k$.

    \item We develop efficient algorithms to approximate low-rank R\'enyi's entropy through random projection and Lanczos iteration techniques, enabling fast and accurate estimations respectively. The overall complexity is reduced from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2s)$ or even $\mathcal{O}(ns^2)$ for some $s \ll n$, leading to a significant speedup compared to the original matrix-based R\'enyi's entropy.

	\item We evaluate the effectiveness of low-rank R\'enyi's entropy on large-scale synthetic and real-world datasets, demonstrating superior performance compared to the original matrix-based R\'enyi's entropy while bringing tremendous improvements in computational efficiency.
\end{itemize}

\section{Related Work}
\subsection{Matrix-based R\'enyi's Entropy}
Given random variable ${\bf X}$ with probability density function (PDF) $p({\bf x})$ defined in a finite set $\mathcal{X}$, the $\alpha$-order R\'enyi's entropy ($\alpha > 0, \alpha \neq 1$) ${\bf H}_\alpha({\bf X})$ is defined as
\begin{equation*}\textstyle
	{\bf H}_{\alpha}({\bf X}) = \frac{1}{1 - \alpha} \log_2 \int_{\mathcal{X}} p^\alpha({\bf x}) \dif {\bf x},
\end{equation*}
where the limit case $\alpha \rightarrow 1$ yields the well-known Shannon's entropy.
It is easy to see that R\'enyi's entropy relies heavily on the distribution of the underlying variable ${\bf X}$, preventing its further adoption in data-driven science, especially for high-dimensional scenarios. To alleviate this issue, an alternative measure namely matrix-based R\'enyi's entropy was proposed \cite{giraldo2014measures}:
\begin{definition} \label{def_renyi}
	Let $\kappa: \mathcal{X} \times \mathcal{X} \mapsto \mathbb{R}$ be an infinitely divisible positive kernel \cite{bhatia2006infinitely}. Given $ \{{\bf x}_i \}_{i=1}^n \subset \mathcal{X}$, each ${\bf x}_i$ being a real-valued scalar or vector, and the Gram matrix $K$ obtained from $K_{ij} = \kappa({\bf x}_i, {\bf x}_j)$, a matrix-based analogue to R\'enyi's $\alpha$-entropy can be defined as:
	\begin{equation*}\textstyle
		{\bf S}_\alpha({\bf A}) = \frac{1}{1-\alpha}\log_2 \Big(\sum_{i=1}^n \lambda_i^\alpha({\bf A}) \Big),
	\end{equation*}
	where ${\bf A}_{ij} = \frac{1}{n}\frac{K_{ij}}{\sqrt{K_{ii}K_{jj}}}$ is a normalized kernel matrix and $\lambda_i({\bf A})$ is the $i$-th largest eigenvalue of ${\bf A}$.
\end{definition}
The kernel matrix ${\bf A}$ is positive semi-definite (PSD) and satisfies ${\bf tr}({\bf A}) = 1$, therefore $\lambda_i \in [0, 1]$ for all $i \in [1,n]$. With this setting, one can similarly define matrix notion of R\'enyi's conditional entropy ${\bf S}_\alpha({\bf A}|{\bf B})$, mutual information ${\bf I}_\alpha({\bf A};{\bf B})$, and their multivariate extensions \cite{yu2019multivariate}.

\subsection{Approximating Matrix-based R\'enyi's Entropy}
Exactly calculating ${\bf S}_\alpha({\bf A})$ requires $\mathcal{O}(n^3)$ time complexity in general with traditional eigenvalue decomposition techniques. Recently, several attempts have been made towards accelerating the computation of ${\bf S}_\alpha({\bf A})$ from the perspective of randomized numerical linear algebra \cite{gong2021computationally, dong2022optimal}. Although we also develop fast approximations, the motivation and technical solutions are totally different: we aim to propose a new measure of information that is robust to noise in data and also enjoys fast computation, whereas Gong and Dong et al. only accelerate the original matrix-based R\'enyi's entropy. Moreover, in terms of adopted mathematical tools, we mainly focus on random projection and Lanczos iteration algorithms, rather than stochastic trace estimation and polynomial approximation techniques used in their works. As a result, the corresponding theoretical error bounds are also different.

\section{A Low-rank Definition of R\'enyi's Entropy}
Our motivations root in two observations. Recall that the min-entropy \cite{konig2009operational}, defined by ${\bf H}_{\mathrm{min}}({\bf X}) = -\log_2 \max_{{\bf x} \in \mathcal{X}} p({\bf x})$, measures the amount of information using solely the largest probability outcome. In terms of quantum statistical mechanics, it is the largest eigenvalue of the quantum state $\rho$ which is PSD and has unit trace \cite{ohya2004quantum}. On the other hand, the eigenvalues with the maximum magnitude characterize the main properties of a PSD matrix. Inspired by these observations, we develop a robust information theoretical quantity by exploiting the low-rank representation:
\begin{definition} \label{def_lowrank}
	Let $\kappa: \mathcal{X} \times \mathcal{X} \mapsto \mathbb{R}$ be an infinitely divisible kernel. Given $\{{\bf x}_i \}_{i=1}^n \subset \mathcal{X}$ and integer $k \in [1, n-1]$, the low-rank R\'enyi's $\alpha$-order entropy is defined as:
	\begin{equation*}\textstyle
		{\bf S}_\alpha^k({\bf A}) = \frac{1}{1-\alpha}\log_2 \prn*{\sum_{i=1}^k \lambda_i^\alpha({\bf A}) + (n-k)\lambda_r^\alpha({\bf A})},
	\end{equation*}
	where ${\bf A}$ is the normalized kernel matrix constructed from $\{{\bf x}_i \}_{i=1}^n$ and $\kappa$, $\lambda_i({\bf A})$ is the $i$-th largest eigenvalues of ${\bf A}$ and $\lambda_r({\bf A}) = \frac{1}{n-k}\big(1 - \sum_{i=1}^k \lambda_i({\bf A}) \big)$.
\end{definition}
Let ${\bf A}_k$ be the best rank-$k$ approximation of ${\bf A}$ and $L_k({\bf A})$ be the matrix constructed by replacing the smaller $n - k$ eigenvalues in ${\bf A}$ to $\lambda_r({\bf A})$. It is easy to verify that ${\bf S}_\alpha^k({\bf A}) = {\bf S}_\alpha^k({\bf A}_k) = {\bf S}_\alpha^k(L_k({\bf A})) = {\bf S}_\alpha(L_k({\bf A}))$. Definition \ref{def_lowrank} complements the smaller eigenvalues through a uniform distribution, which is the \textbf{unique method} that fulfills all axioms below (the uniqueness is discussed in the appendix\footnote{\url{https://github.com/Gamepiaynmo/LRMI}}).
\begin{proposition} \label{prop_lowrank}
    Let ${\bf A}, {\bf B} \in \mathbb{R}^{n \times n}$ be arbitrary normalized kernel matrices, then
    \begin{enumerate}[(a)]
        \item ${\bf S}_\alpha^k({\bf P}{\bf A}{\bf P}^\top) = {\bf S}_\alpha^k({\bf A})$ for any orthogonal matrix ${\bf P}$.
        \item ${\bf S}_\alpha^k(p{\bf A})$ is a continuous function for $0 < p \le 1$.
        \item $0 \le {\bf S}_\alpha^k({\bf A}) \le {\bf S}_\alpha^k(\frac{1}{n}{\bf I}) = \log_2(n)$.
        \item ${\bf S}_\alpha^{2nk-k^2}\big(L_k({\bf A}) \otimes L_k({\bf B})\big) = {\bf S}_\alpha^k({\bf A}) + {\bf S}_\alpha^k({\bf B})$.
        \item If ${\bf A}{\bf B} = {\bf B}{\bf A} = \mathbf{0}$ and ${\bf tr}({\bf A}_k) = {\bf tr}({\bf B}_k) = 1$, then for $g(x) = 2^{(1-\alpha)x}$ and $t \in [0, 1]$, we have ${\bf S}_\alpha^{2k}\big(t{\bf A} + (1-t){\bf B}\big) = g^{-1}\big( tg({\bf S}_\alpha^k({\bf A})) + (1-t)g({\bf S}_\alpha^k({\bf B})) \big)$.
        \item ${\bf S}_\alpha^k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}} \ge \max\prn*{{\bf S}_\alpha^k({\bf A}), {\bf S}_\alpha^k({\bf B})}$.
        \item ${\bf S}_\alpha^k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}} \le {\bf S}_\alpha^k({\bf A}) + {\bf S}_\alpha^k({\bf B})$.
    \end{enumerate}
\end{proposition}

\begin{remark}
    Proposition \ref{prop_lowrank} characterizes the basic properties of low-rank R\'enyi's entropy, in which (a)-(e) are the set of axioms provided by R\'enyi \cite{renyi1961measures} that a function must satisfy to be a measure of information. Additionally, (f) and (g) together imply a definition of joint entropy which is also compatible with the individual entropy measures:
    \begin{equation*}\textstyle
        {\bf S}_\alpha^k({\bf A}, {\bf B}) = {\bf S}_\alpha^k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}}.
    \end{equation*}
    This further allows us to define the low-rank conditional entropy ${\bf S}_\alpha^k({\bf A}|{\bf B})$ and mutual information ${\bf I}_\alpha^k({\bf A};{\bf B})$, whose positiveness is guaranteed by (f) and (g) respectively:
    \begin{gather*}
        {\bf S}_\alpha^k({\bf A}|{\bf B}) = {\bf S}_\alpha^k({\bf A}, {\bf B}) - {\bf S}_\alpha^k({\bf B}), \\
        {\bf I}_\alpha^k({\bf A};{\bf B}) = {\bf S}_\alpha^k({\bf A}) + {\bf S}_\alpha^k({\bf B}) - {\bf S}_\alpha^k({\bf A}, {\bf B}).
    \end{gather*}
\end{remark}

An intuitive overview of the comparative behavior between ${\bf S}_\alpha({\bf A})$ and ${\bf S}_\alpha^k({\bf A})$ for $n = 1000$ is reported in Figure \ref{fig_intuitive} and \ref{fig_intuitive1}, where we evaluate the impact of $k$, $\alpha$ and eigenspectrum decay rate (EDR) $r$ respectively. The eigenvalues are initialized by $\lambda_i = e^{-ri/n}$ and then normalized. It can be observed from Figure \ref{fig_intuitive} that ${\bf S}_\alpha^k({\bf A})$ is always larger than ${\bf S}_\alpha({\bf A})$ since the uncertainty of the latter $n - k$ outcomes are maximized. Moreover, ${\bf S}_\alpha^k({\bf A})$ quickly converges to ${\bf S}_\alpha({\bf A})$ with the increase of $k$, especially in extreme cases when the eigenspectrum of ${\bf A}$ is flat or steep. From Figure \ref{fig_intuitive1}, we can see that for small $k$, ${\bf S}_\alpha^k({\bf A})$ decreases slow with the increase of $\alpha$ when $\alpha < 1$ and fast otherwise. This behavior is the opposite when $k$ becomes large. Furthermore, we can see that EDR directly influences the value of entropy, as a flat eigenspectrum indicates higher uncertainty and steep the opposite. As can be seen, ${\bf S}_\alpha^k({\bf A})$ monotonically decreases with the increase of $r$, and decreases faster than ${\bf S}_\alpha({\bf A})$ in a certain range which varies according to the choice of $k$, indicating higher sensitivity to informative distribution changes when the hyper-parameter $k$ is selected properly.

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.45\textwidth]{results/intuitive.pdf}
	\caption{Left: PDF (solid) and CDF (dashed) of the altered eigenspectrum for different ranks $k$. Right: The convergence behavior of ${\bf S}_\alpha^k({\bf A})$ (solid) to ${\bf S}_\alpha({\bf A})$ (dashed) with the increase of rank $k$ for different EDR ($r$).}
	\label{fig_intuitive}
\end{figure}

Moreover, consider the case that the data samples $\{{\bf x}_i\}_{i=1}^n$ are randomly perturbed, i.e. ${\bf y}_i = {\bf x}_i + \varepsilon{\bf p}_i$, where ${\bf p}_i$ are random vectors comprised of i.i.d. entries with zero expectation and unit variance. Let ${\bf A}$ and ${\bf B}$ be kernel matrices constructed from $\{{\bf x}_i\}_{i=1}^n$ and $\{{\bf y}_i\}_{i=1}^n$ respectively, and let $\{\lambda_i\}_{i=1}^n$, $\{\mu_i\}_{i=1}^n$ be their eigenvalues. Then it satisfies that $\mu_i \approx \lambda_i + {\bf u}_i^\top({\bf B}-{\bf A}){\bf u}_i$ \cite{ngo2005approach}, where ${\bf u}_i$ is the corresponding eigenvector of $\lambda_i$. When $\varepsilon$ is small, the entries as well as the eigenvalues of ${\bf A}$ are nearly independently perturbed. The following theorem shows that ${\bf S}_\alpha^k({\bf A})$ is more robust against small noises in data compared to ${\bf S}_\alpha({\bf A})$:
\begin{theorem} \label{th:robust}
    Let $\{\nu_i\}_{i=1}^n$ be independent random variables with zero mean and variance $\{\sigma_i^2\}_{i=1}^n$. Let ${\bf A}$ and ${\bf B}$ be PSD matrices with eigenvalues $\lambda_i$ and $\mu_i = \lambda_i + \nu_i$ respectively. If $\sum_{i=1}^k\sigma_i^2 \le \sum_{i=k+1}^n\sigma_i^2$ or $\alpha > 1$, there exists $\epsilon > 0$ such that when all $|\nu_i| \le \epsilon$, we have ${\bf Var}[{\bf IP}_\alpha^k({\bf B})] \le {\bf Var}[{\bf IP}_\alpha({\bf B})]$, where ${\bf IP}$ is the information potential \cite{gokcay2000new} defined as ${\bf IP}_\alpha({\bf B}) = 2^{(1-\alpha){\bf S}_\alpha({\bf B})}$ and ${\bf IP}_\alpha^k({\bf B}) = 2^{(1-\alpha){\bf S}_\alpha^k({\bf B})}$.
\end{theorem}
\begin{remark}
    Theorem \ref{th:robust} indicates that ${\bf IP}_\alpha^k({\bf B})$ enables lower variance than ${\bf IP}_\alpha({\bf B})$ against random perturbation of the eigenvalues under mild conditions, which is easy to be satisfied since in most cases we have $k \ll n$. Combining with our discussion above, the low-rank R\'enyi's entropy is more sensitive to informative variations in probability distributions which will surely induce an increase or decrease in entropy, while being insensitive to uninformative perturbations caused by noises in the data samples.
\end{remark}

\subsection{Extending to Multivariate Scenarios}
Following Definition \ref{def_lowrank} and Proposition \ref{prop_lowrank}, the low-rank variant of multivariate R\'enyi's joint entropy, in virtue of the Venn diagram relation for Shannon's entropy \cite{yeung1991new}, could be naturally derived:
\begin{definition} \label{def_lowrank_joint}
	Let $\{\kappa_i\}_{i=1}^L: \mathcal{X}^i \times \mathcal{X}^i \mapsto \mathbb{R}$ be positive infinitely divisible kernels and $\{{\bf x}_i^1, \cdots, {\bf x}_i^L\}_{i=1}^n \subset \mathcal{X}^1 \times \cdots \times \mathcal{X}^L$, the low-rank R\'enyi's joint entropy is defined as:
	\begin{equation*}\textstyle
		{\bf S}_\alpha^k({\bf A}_1, \cdots, {\bf A}_L) = {\bf S}_\alpha^k \prn*{\frac{{\bf A}_1 \circ \cdots \circ {\bf A}_L}{\mathbf{tr}({\bf A}_1 \circ \cdots \circ {\bf A}_L)}},
	\end{equation*}
    where ${\bf A}_1, \cdots, {\bf A}_L$ are normalized kernel matrices constructed from $\{{\bf x}_i^1\}_{i=1}^n$, $\cdots$, $\{{\bf x}_i^L\}_{i=1}^n$ respectively and $\circ$ denotes the Hadamard product.
\end{definition}

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.45\textwidth]{results/intuitive1.pdf}
	\caption{Left: The behavior of ${\bf S}_\alpha^k({\bf A})$ when the entropy order $\alpha$ varies from $0$ to $2$. Right: The behavior of ${\bf S}_\alpha^k({\bf A})$ when the EDR of ${\bf A}$ varies from flat to steep.}
	\label{fig_intuitive1}
\end{figure}

This joint entropy definition enables further extension to multivariate conditional entropy and mutual information:
\begin{gather*}
    {\bf S}_\alpha^k({\bf A}_1, \cdots, {\bf A}_k| {\bf B}) = {\bf S}_\alpha^k({\bf A}_1, \cdots, {\bf A}_k, {\bf B}) - {\bf S}_\alpha^k({\bf B}), \\
    \begin{aligned}
    	{\bf I}_\alpha^k({\bf A}_1, \cdots, {\bf A}_k; {\bf B}) =&\, {\bf S}_\alpha^k({\bf A}_1, \cdots, {\bf A}_k) + {\bf S}_\alpha^k({\bf B}) \\
    	&- {\bf S}_\alpha^k({\bf A}_1, \cdots, {\bf A}_k, {\bf B}),
    \end{aligned}
\end{gather*}
where ${\bf A}_1, \cdots, {\bf A}_L$ and ${\bf B}$ are normalized kernel matrices constructed from the variables $\{{\bf x}_i^1\}_{i=1}^n$, $\cdots$, $\{{\bf x}_i^L\}_{i=1}^n$ and the target label $\{{\bf y}_i\}_{i=1}^n$ respectively. Their positiveness can be guaranteed through a reduction to axiom (f) and (g). These multivariate information quantities enable much more widespread applications e.g. feature selection, dimension reduction and information-based clustering.

\section{Approximating Low-rank R\'enyi's Entropy}
Although only the largest eigenvalues are accessed by our entropy definition, one still needs to calculate the full eigenspectrum of the PSD matrix ${\bf A}$ through eigenvalue decomposition algorithms, resulting in $\mathcal{O}(n^3)$ overall time cost. To alleviate the computational burden, we design fast approximations by leveraging random projection and Lanczos iteration techniques for low-rank R\'enyi's entropy.

\subsection{Random Projection Approach}
Random projection offers a natural way to approximate the low-rank representation of kernel matrices. The core idea is to project the $n \times n$ PSD matrix ${\bf A}$ into a $n \times s$ subspace, and then use the largest $k$ singular value of the projected matrix as approximations of the largest $k$ eigenvalues, as summarized in Algorithm \ref{alg_proj}. In this way, the main computation cost is reduced to $\mathcal{O}(n^2s)$ or even $\mathcal{O}(ns^2)$, ($s \ll n$), substantially lower than the original $\mathcal{O}(n^3)$ approach. Based on this fact, we develop efficient approximation algorithms by exploring different random projection techniques, in which the construction of ${\bf P}$ varies depending on the practical applications, ranging from simple but effective Gaussian distributions to advanced random orthogonal projections.

\begin{algorithm}[t]
	\begin{algorithmic}[1]
		\STATE \textbf{Input:} Integers $n$, $k \in [1,n/2], s \ge k$, kernel matrix ${\bf A} \in \mathbb{R}^{n \times n}$, order $\alpha > 0$.
		\STATE \textbf{Output:} Approximation to ${\bf S}_\alpha^k({\bf A})$;

		\STATE Construct a random projection matrix ${\bf P} \in \mathbb{R}^{n \times s}$.
		\STATE Calculate $\hat{{\bf A}} =  {\bf A} {\bf P} \in \mathbb{R}^{n \times s}$.
		\STATE Calculate the largest $k$ singular values $\hat{\lambda}_i$, $i \in [1,k]$ of $\hat{{\bf A}}$ through singular value decomposition.
		\STATE Calculate $\hat{\lambda}_r = \frac{1}{n-k}\prn*{1 - \sum_{i=1}^{k} \hat{\lambda}_i}$.

		\STATE \textbf{Return:} $\hat{{\bf S}}_\alpha^k({\bf A}) = \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^{k} \hat{\lambda}_i^\alpha + (n-k)\hat{\lambda}_r^\alpha}$.
	\end{algorithmic}
	\caption{Approximation via Random Projection}
	\label{alg_proj}
\end{algorithm}

\subsubsection{Gaussian Random Projection} \leavevmode\\
As one of the most widely used random projection techniques, Gaussian random projection (GRP) admits a simple but elegant solution for eigenvalue approximation:
\begin{equation*}\textstyle
    {\bf P} = \sqrt{n/s} \cdot {\bf G},
\end{equation*}
where the columns of ${\bf G} \in \mathbb{R}^{n \times s}$ are initialized by i.i.d random standard Gaussian variables and then orthogonalized. The time complexity of GRP is $\mathcal{O}(n^2s)$.

\subsubsection{Subsampled Randomized Hadamard Transform} \leavevmode\\
SRHT \cite{lu2012faster, tropp2011improved} is a simplification of the fast Johnson-Lindenstrauss transform \cite{ailon2009fast} which
preserves the geometry of an entire subspace of vectors compared to GRP. In our settings, the $n \times s$ SRHT matrix is constructed by
\begin{equation*}\textstyle
	{\bf P} = \sqrt{1/s} \cdot {\bf D} {\bf H} {\bf S},
\end{equation*}
where ${\bf D} \in \mathbb{R}^{n \times n}$ is a diagonal matrix with random $\{\pm 1 \}$ entries, ${\bf H} \in \mathbb{R}^{n \times n}$ is a Walsh-Hadamard matrix, ${\bf S} \in \mathbb{R}^{n \times s}$ is a subsampling matrix whose columns are a uniformly chosen subset of the standard basis of $\mathbb{R}^n$.

Two key ingredients make SRHT an efficient approximation strategy: first, it takes only $\mathcal{O}(n^2 \min(\log(n),s))$ time complexity to calculate the projected matrix $\hat{{\bf A}}$; second, the orthonormality between the columns of ${\bf A}$ can be preserved after projection, thus is more likely to achieve lower approximation error compared to GRP.

\subsubsection{Input-Sparsity Transform} \leavevmode\\
Similar to SRHT, input-sparsity transform (IST) \cite{mahoney2011randomized, woodruff2020near} utilizes the fast John-Lindenstrauss transform to reduce time complexity for least-square regression and low-rank approximation:
\begin{equation*}\textstyle
    {\bf P} = \sqrt{n/s} \cdot {\bf D} {\bf S},
\end{equation*}
where ${\bf D}$ and ${\bf S}$ are constructed in the same way as SRHT. The complexity of calculating $\hat{{\bf A}}$ using IST is $\mathcal{O}(\textrm{nnz}({\bf A}))$, where nnz denotes the number of non-zero entries, resulting in a total complexity of $\mathcal{O}(\min(\textrm{nnz}({\bf A}), ns^2))$.

\subsubsection{Sparse Graph Sketching} \leavevmode\\
The idea of using sparse graphs as sketching matrices is proposed in \cite{hu2021sparse}. It is shown that the generated bipartite graphs by uniformly adding edges enjoy elegant theoretical properties known as the Expander Graph or Magical Graph with high probability, and thus serve as an effective random projection strategy:
\begin{equation*}\textstyle
    {\bf P} = \sqrt{1/p} \cdot {\bf G},
\end{equation*}
where $p \in \mathbb{N}$ is the hyper-parameter that controls the sparsity, and each column ${\bf g}$ of ${\bf G}$ is constructed independently by uniformly sampling $c \subset [n]$ with $|c| = p$, and then setting ${\bf g}_i = \{\pm 1\}$ randomly for $i \in c$ and ${\bf g}_i = 0$ for $i \notin c$. Similar to IST, sparse graph sketching (SGS) also utilizes the sparsity of input matrices and achieves $\mathcal{O}(\textrm{nnz}({\bf A})p)$ computational complexity to calculate the projected matrix.

\subsubsection{Theoretical Results} \leavevmode\\
Next, we provide the main theorem on characterizing the quality-of-approximation for low-rank R\'enyi's entropy:
\begin{theorem} \label{th:rp_approx}
	Let ${\bf A}$ be positive definite and
	\begin{gather*}
	    s = \begin{cases}
	        \mathcal{O}(k + \log(1/\delta)/\epsilon_0^2), & \textrm{for GRP} \\
	        \mathcal{O}((k + \log n)\log k/\epsilon_0^2), & \textrm{for SRHT} \\
	        \mathcal{O}(k^2/\epsilon_0^2), & \textrm{for IST} \\
	        \mathcal{O}(k\log(k/\delta\epsilon_0)/\epsilon_0^2), & \textrm{for SGS}
	    \end{cases} \\
	    p = \mathcal{O}(\log(k/\delta\epsilon_0)/\epsilon_0), \qquad\textrm{for SGS}
	\end{gather*}
	where $\epsilon_0 = \epsilon\lambda_k\lambda_r$, then for $k \le n/2$, with confidence at least $1-\delta$, the output of Algorithm \ref{alg_proj} satisfies
	\begin{equation*}
		|\lambda_i^2 - \hat{\lambda}_i^2 | \leq \epsilon
	\end{equation*}
	for all $i \in [1,k]$ eigenvalues of ${\bf A}$ and
	\begin{equation*}\textstyle
		|{\bf S}_\alpha^k({\bf A}) - \hat{{\bf S}}_\alpha^k({\bf A})| \leq \abs{\frac{\alpha}{1-\alpha} \log_2 \prn*{1-\epsilon}}.
	\end{equation*}
\end{theorem}

\begin{remark}
	Theorem \ref{th:rp_approx} provides the accuracy guarantees for low-rank R\'enyi's entropy approximation via random projections. It can be observed that the approximation error grows with the increase of $\alpha$ when $\alpha$ is small. Note that although the error bound is additive in nature, it can be further reduced to a relative error bound under mild condition ${\bf S}_\alpha^k(G) \geq \sqrt{\epsilon}$. In general, Theorem \ref{th:rp_approx} requires $s = \mathcal{O}(k + 1/\epsilon^2)$ to achieve $1\pm\epsilon$ absolute accuracy, which is consistent with the complexity results of least squares and low rank approximations \cite{mahoney2011randomized}.
\end{remark}

\subsection{Lanczos Iteration Approach}
Besides random projection, the Lanczos algorithm is also widely adopted to find the $k$ extreme (largest or smallest in magnitude) eigenvalues and the corresponding eigenvectors of an $n \times n$ Hermitian matrix ${\bf A}$. Given an initial vector ${\bf q}$, the Lanczos algorithm utilizes the Krylov subspace spanned by $\{{\bf q}, {\bf A}{\bf q}, \cdots, {\bf A}^s{\bf q}\}$ to construct an tridiagonalization of ${\bf A}$ whose eigenvalues converge to those of ${\bf A}$ along with the increase of $s$, and are satisfactorily accurate even for $s \ll n$. As shown in Algorithm \ref{alg_lanczos}, the main computation cost is the $\mathcal{O}(n^2s)$ matrix-vector multiplications in the Lanczos process, which could be further reduced to $\mathcal{O}(\mathrm{nnz}({\bf A})s)$ when ${\bf A}$ is sparse. The computational cost of reorthogonalization can be further alleviated by explicit or implicit restarting Lanczos methods. The following theorem establishes the accuracy guarantee of Algorithm \ref{alg_lanczos}:

\begin{algorithm}[t]
    \caption{Approximation via Lanczos Iteration}
    \label{alg_lanczos}
    \begin{algorithmic}[1]
    	\STATE \textbf{Input:} Integers $n$, $k \in [1,n/2], s \ge k$, kernel matrix ${\bf A} \in \mathbb{R}^{n \times n}$, order $\alpha > 0$, initial vector ${\bf q}$.
    	\STATE \textbf{Output:} Approximation to ${\bf S}_\alpha^k(G)$.

    	\STATE Set ${\bf q}_0 = 0, \beta_0 = 0, {\bf q}_1 = {\bf q} / \norm{{\bf q}}$.
    	\FOR{$j = 1, 2, \cdots, s$}
    	\STATE $\hat{{\bf q}}_{j+1} = {\bf A}{\bf q}_j - \beta_{j-1}{\bf q}_{j-1}$, $\gamma_j = \ang{\hat{{\bf q}}_{j+1}, {\bf q}_j}$.
    	\STATE $\hat{{\bf q}}_{j+1} = \hat{{\bf q}}_{j+1} - \gamma_j{\bf q}_j$.
    	\STATE Orthogonalize $\hat{{\bf q}}_{j+1}$ against ${\bf q}_1, \cdots, {\bf q}_{j-1}$.
    	\STATE $\beta_j = \norm{\hat{{\bf q}}_{j+1}}$, ${\bf q}_{j+1} = \hat{{\bf q}}_{j+1} / \beta_j$.
    	\ENDFOR
    	\STATE Calculate the largest $k$ eigenvalues $\hat{\lambda}_i$, $i \in [1, k]$ of \\
    	$\qquad {\bf T} = \begin{bmatrix}
            \gamma_1 & \beta_1 & & 0 \\
            \beta_1 & \gamma_2 & & \\
            & & \ddots & \beta_{s-1} \\
            0 & & \beta_{s-1} & \gamma_s \\
        \end{bmatrix}$.
		\STATE Calculate $\hat{\lambda}_r = \frac{1}{n-k}\prn*{1 - \sum_{i=1}^{k} \hat{\lambda}_i}$.

		\STATE \textbf{Return:} $\hat{{\bf S}}_\alpha^k({\bf A}) = \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^{k} \hat{\lambda}_i^\alpha + (n-k)\hat{\lambda}_r^\alpha}$.
    \end{algorithmic}
\end{algorithm}

\begin{theorem} \label{th:lanczos_approx}
    Let ${\bf A}$ be positive definite, ${\bf q}$ be the initial vector, $\{\bm{\phi}_i\}_{i=1}^k$ be the corresponding eigenvectors and
    \begin{equation*}
        \textstyle
        s = \ceil*{k + \frac{1}{2\log R} \log\prn*{\frac{4\theta^2K^2\lambda_1}{\epsilon\lambda_r}}},
    \end{equation*}
    where
    \begin{gather*}
        \textstyle
        R = \gamma + \sqrt{\gamma^2 - 1}, \quad \gamma = 1 + 2\min_{i\in[1,k]} \frac{\lambda_i - \lambda_{i+1}}{\lambda_{i+1} - \lambda_n}, \\
        \textstyle
        \theta = \max_{i\in[1,k]} \tan\ang{\bm{\phi}_i, {\bf q}}, \quad K = \prod_{j=1}^{k-1} \frac{\hat{\lambda}_j - \lambda_n}{\hat{\lambda}_j - \lambda_k},
    \end{gather*}
    then for $k \le n/2$, the output of Algorithm \ref{alg_lanczos} satisfies\begin{equation*}
        \textstyle
		0 \le \lambda_i - \hat{\lambda}_i \leq \epsilon \lambda_i
	\end{equation*}
	for all $i \in [1,k]$ eigenvalues of ${\bf A}$ and
	\begin{equation*}\textstyle
		|{\bf S}_\alpha^k({\bf A}) - \hat{{\bf S}}_\alpha^k({\bf A})| \leq \abs{\frac{\alpha}{1-\alpha} \log_2 \prn*{1-\epsilon}}.
	\end{equation*}
\end{theorem}

\begin{remark}
    Theorem \ref{th:lanczos_approx} provides the accuracy guarantee for the Lanczos algorithm. The relationship between approximation error and $\alpha$ is similar to those in Theorem \ref{th:rp_approx}. Algorithm \ref{alg_lanczos} achieves a much faster convergence rate compared to Algorithm \ref{alg_proj} while achieving the same level of absolute precision. When $\epsilon$ is small, $R$, $\theta$ and $K$ can be regarded as constants that depends only on the eigenspectrum of ${\bf A}$ and the initial vector ${\bf q}$, so that $s = \mathcal{O}(k + \log(1/\epsilon))$ is enough to guarantee a $1\pm\epsilon$ accuracy. In practice, ${\bf q}$ is suggested to be generated by random Gaussian in order to avoid a large $\theta$ with high probability \cite{urschel2021uniform}.
\end{remark}

\section{Experimental Results}
In this section, we evaluate the proposed low-rank R\'enyi's entropy and the approximation algorithms under large-scale experiments. Our experiments are conducted on an Intel i7-10700 (2.90GHz) CPU and an RTX 2080Ti GPU with 64GB of RAM. The algorithms are implemented in C++ with the Eigen library and in Python with the Pytorch library.

\subsection{Simulation studies}
We first test the robustness of ${\bf S}_\alpha^k({\bf A})$ against noises in the data. As indicated by Theorem \ref{th:robust}, low-rank R\'enyi's entropy achieves lower variance under mild conditions in terms of the information potential. We consider the case that the input data points are randomly perturbed, i.e. ${\bf y}_i = {\bf x}_i + \varepsilon{\bf p}_i$ for $i \in [1, n]$, where ${\bf p}_i$ is comprised of i.i.d. random variables. Let $\{\lambda_i\}_{i=1}^n$, $\{\mu_i\}_{i=1}^n$ denote the eigenvalues of normalized kernel matrices constructed from $\{{\bf x}_i\}_{i=1}^n$ and $\{{\bf y}_i\}_{i=1}^n$ respectively. We test the following noise distributions: Standard Gaussian $N(0,1)$, Uniform $U(-\sqrt{3}, \sqrt{3})$, Student-t $t(3)/\sqrt{3}$ and Rademacher $\{\pm 1\}$ with $n = 100$ (detailed settings are given in the appendix). The examples of variation in eigenvalues ($\mu_i - \lambda_i$) and the standard deviation (multiplied by $n$) of entropy values after $100$ trials are reported in Figure \ref{fig_variance}. It verifies our analysis that when $\varepsilon$ is small, the eigenvalues $\mu_i$ are nearly independently perturbed. Moreover, our low-rank definition achieves lower variance than matrix-based R\'enyi's entropy under different choices of $\alpha$, in which smaller $k$ corresponds to higher robustness.

\begin{figure*}[t]
	\small
	\centering
	\includegraphics[width=0.9\textwidth]{results/variance.pdf}
	\caption{Upper: perturbation of the eigenvalues, i.e. $\mu_i - \lambda_i$. Lower: standard deviation of matrix-based R\'enyi's entropy and low-rank R\'enyi's entropy against random perturbations of the data samples for different values of $\alpha$.}
	\label{fig_variance}
\end{figure*}

\subsection{Real Data Examples}
In this section, we demonstrate the great potential of applying our low-rank R\'enyi's entropy functional and its multivariate extensions in two representative real-world information-related applications, which utilize the mutual information (information bottleneck) and multivariate mutual information (feature selection) respectively.

\begin{table}[t]
    \centering
    \small
	\setlength{\tabcolsep}{0.7em}
    \begin{tabular}{ccc}
        \toprule
        Objective & Accuracy (\%) & Training Time (minutes) \\
        \midrule
        CE & 92.64 $\pm$ 0.03 & \hphantom{0}- / \hphantom{0}80 \\
        VIB & 94.08 $\pm$ 0.02 & \hphantom{0}4 / \hphantom{0}84 \\
        NIB & 94.01 $\pm$ 0.04 & \hphantom{0}7 / \hphantom{0}87 \\
        \midrule
        MRIB & \ul{94.13 $\pm$ 0.04} & 46 / 126 \\
        LRIB & \bf{94.16 $\pm$ 0.09} & 15 / \hphantom{0}95 \\
		\bottomrule
    \end{tabular}
    \caption{Classification accuracy and training time of different IB objectives. Left is the time spent on IB calculation and right is the total training time.}
    \label{tbl_ib}
\end{table}

\begin{table*}[t]
	\centering
	\footnotesize
	\setlength{\tabcolsep}{0.27em}
	\begin{tabular}{ ccccccccccc }
		\toprule
		Method & Criterion & Breast & Semeion & Madelon & Krvskp & Spambase & Waveform & Optdigits & Statlog & Average \\
		\midrule
		MIFS & $\scriptstyle {\bf I}({\bf X}_{i_l};{\bf Y}) - \beta \sum_{j=1}^{l-1} {\bf I}({\bf X}_{i_l};{\bf X}_{i_j})$ & 4.8 & 2.5 & 6.6 & 3.8 & 7.3 & 6.4 & 4.5 & 3.8 & 4.96 \\
		FOU & $\scriptstyle {\bf I}({\bf X}_{i_l};{\bf Y}) - \sum_{j=1}^{l-1} [{\bf I}({\bf X}_{i_l};{\bf X}_{i_j}) - {\bf I}({\bf X}_{i_l};{\bf X}_{i_j}|{\bf Y})]$ & 5.2 & 2.5 & 5.6 & 1.9 & 6.2 & 5.7 & 4.8 & 5.7 & 4.70 \\
		MRMR & $\scriptstyle {\bf I}({\bf X}_{i_l};{\bf Y}) - \frac{1}{l-1} \sum_{j=1}^{l-1} {\bf I}({\bf X}_{i_l};{\bf X}_{i_j})$ & \bf{2.3} & 4.7 & 6.7 & 3.7 & 5.6 & 3.6 & 4.8 & 4.0 & 4.43 \\
		JMI & $\scriptstyle \sum_{j=1}^{l-1} {\bf I}(\{{\bf X}_{i_l},{\bf X}_{i_j}\};{\bf Y})$ & 5.1 & 5.2 & 3.0 & 3.7 & 4.2 & 2.3 & 3.8 & 3.5 & 3.85 \\
		CMIM & $\scriptstyle \min_{j=1}^{l-1} {\bf I}({\bf X}_{i_l};{\bf Y}|{\bf X}_{i_j})$ & 3.0 & 2.7 & 4.5 & 3.6 & 3.2 & 4.7 & 2.6 & 5.6 & 3.74 \\
		DISR & $\scriptstyle \sum_{j=1}^{l-1} {\bf I}(\{{\bf X}_{i_l},{\bf X}_{i_j}\};{\bf Y}) / {\bf H}({\bf X}_{i_l},{\bf X}_{i_j},{\bf Y})$ & 7.3 & 5.7 & 4.0 & 3.2 & 3.9 & 2.3 & 6.9 & 5.8 & 4.89 \\
		\midrule
		MRMI & $\scriptstyle {\bf I}_\alpha(\{{\bf X}_{i_1},{\bf X}_{i_2},\cdots,{\bf X}_{i_l}\};{\bf Y})$ & \ul{2.6} & \ul{1.8} & \ul{1.2} & \ul{1.7} & \bf{1.5} & \ul{1.8} & \bf{1.3} & \bf{2.0} & \ul{1.74} \\
		LRMI & $\scriptstyle {\bf I}_\alpha^k(\{{\bf X}_{i_1},{\bf X}_{i_2},\cdots,{\bf X}_{i_l}\};{\bf Y})$ & \ul{2.6} & \bf{1.4} & \bf{1.1} & \bf{1.6} & \bf{1.5} & \bf{1.5} & \bf{1.3} & \ul{2.1} & \bf{1.64} \\
		\bottomrule
	\end{tabular}
	\caption{Information theoretic feature selection methods and their average rank over different number of features in each dataset. The first and second best performances are marked as \textbf{bold} and \ul{underlined} respectively.}
	\label{tbl_selection}
\end{table*}

\subsubsection{Application to Information Bottleneck} \leavevmode\\
The Information Bottleneck (IB) methods recently achieve great success in compressing redundant or irrelevant information in the inputs and preventing overfitting in deep neural networks. Formally, given network input ${\bf X}$ and target label ${\bf Y}$, the IB approach tries to extract a compressed intermediate representation ${\bf Z}$ from ${\bf X}$ that maintains minimal yet meaningful information to predict the task ${\bf Y}$ by optimizing the following IB Lagrangian:
\begin{equation*}
    \mathcal{L}_{\textrm{IB}} = {\bf I}({\bf Y}, {\bf Z}) - \beta \cdot {\bf I}({\bf X}, {\bf Z}),
\end{equation*}
where $\beta$ is the hyper-parameter that balances the trade-off between \textbf{sufficiency} (predictive performance of ${\bf Z}$ on task ${\bf Y}$, quantified by ${\bf I}({\bf Y}, {\bf Z})$) and \textbf{minimality} (the complexity of ${\bf Z}$, quantified by ${\bf I}({\bf X}, {\bf Z})$). In practice, optimizing ${\bf I}({\bf Y}, {\bf Z})$ is equivalent to the cross-entropy (CE) loss for classification tasks, so our target remains to optimize the latter term ${\bf I}({\bf X}, {\bf Z})$. However, mutual information estimation is extremely hard or even intractable for high-dimension distributions, which is usually the case in deep learning. To address this issue, there have been efforts on using variational approximations to optimize a lower bound of ${\bf I}({\bf X}, {\bf Z})$, e.g. Variational IB (VIB) \cite{alemi2017deep} and Nonlinear IB (NIB) \cite{kolchinsky2019nonlinear}. We show that with low-rank R\'enyi's entropy, ${\bf I}({\bf X}, {\bf Z})$ can be directly optimized by approximating the largest $k$ eigenvalues of the kernel matrix ${\bf A}$ constructed by ${\bf X}$ and ${\bf Z}$. Recall that the Lanczos method constructs an approximation ${\bf A} \approx {\bf Q}{\bf T}{\bf Q}^\top$, where ${\bf Q} \in \mathbb{R}^{n \times s}$ has orthogonal columns and ${\bf T} \in \mathbb{R}^{s \times s}$ is tridiagonal, we have $\hat{\lambda}_i = \lambda_i({\bf Q}^\top{\bf A}{\bf Q})$ for all $i \in [1,s]$. Let $\sum_{i=1}^s\hat{\lambda}_i{\bf u}_i{\bf u}_i^\top$ be the eigenvalue decomposition of ${\bf Q}^\top{\bf A}{\bf Q}$, we can approximate the gradient of ${\bf S}_\alpha^k({\bf A})$ as:
\begin{equation*}
    \frac{\partial{\bf S}_\alpha^k({\bf A})}{\partial{\bf A}} \approx \sum_{i=1}^k \frac{\partial\hat{{\bf S}}_\alpha^k({\bf A})}{\partial\hat{\lambda}_i} \cdot {\bf Q}{\bf u}_i{\bf u}_i^\top{\bf Q}^\top.
\end{equation*}
In this experiment, we test the performance of matrix-based R\'enyi's IB (MRIB) \cite{yu2021deep} and our low-rank variant (LRIB) with variational approximation-based objectives using VGG16 as the backbone and CIFAR10 as the classification task. All models are trained for $300$ epochs with $100$ batch size and $0.1$ initial learning rate which is divided by $10$ every $100$ epochs. Following the settings in \cite{yu2021deep}, we select $\alpha = 1.01$, $\beta = 0.01$, $k = 10$ and $s = 20$. The final results are reported in Table \ref{tbl_ib}. It can be seen that the matrix-based approaches MRIB and LRIB outperform other methods, while our LRIB achieves the highest performance with significantly less training time.

\subsubsection{Application to Feature Selection} \leavevmode\\
In practical regression or classification machine learning tasks, many features can be completely irrelevant to the learning target or redundant in the context of others. Given a set of features ${\bf S} = \{{\bf X}_1, \cdots, {\bf X}_L\}$ and the target label ${\bf Y}$, we aim to find a subset ${\bf S}_{sub} \subset {\bf S}$ which leverage the expressiveness and the complexity simultaneously. In the field of information theoretic learning, this target is equivalent to maximizing the multivariate mutual information ${\bf I}({\bf S}_{sub};{\bf Y})$, which is computationally prohibitive due to the curse of high dimensionality. As a result, there have been tremendous efforts on approximation techniques that retain only the first or second order interactions and build mutual information estimators upon low-dimensional probability distributions, including Mutual Information-based Feature Selection (MIFS) \cite{battiti1994using}, First-Order Utility (FOU) \cite{brown2009new}, Maximum-Relevance Minimum-Redundancy (MRMR) \cite{peng2005feature}, Joint Mutual Information (JMI) \cite{yang1999data}, Conditional Mutual Information Maximization (CMIM) \cite{fleuret2004fast} and Double Input Symmetrical Relevance (DISR) \cite{meyer2006use} which achieve state-of-the-art performance in information-based feature selection tasks.

We evaluate the performance of matrix-based R\'enyi's mutual information (MRMI) and our low-rank variant (LRMI) with these methods on $8$ widely-used classification datasets as shown in Table \ref{tbl_dataset}, which is chosen to cover a broad variety of instance-feature ratios, number of classes and discreteness. Notice that non-R\'enyi methods can only handle discrete features, so we discretize them into $5$ bins under equal-width criterion as adopted in \cite{brown2012conditional}. In this experiment, we choose the Support Vector Machine (SVM) algorithm with RBF kernel ($\sigma = 1$) as the classifier for continuous datasets and a 3-NN classifier for discrete datasets. Following the settings of \cite{yu2019multivariate}, we select $\alpha \in \{0.6, 1.01, 2\}$, $k \in \{100, 200, 400\}$ via cross-validation, $s = k + 50$ and use the Gaussian kernel of width $\sigma = 1$ for matrix-based entropy measures. Considering that it is NP-hard to evaluate each subset of ${\bf S}$, we adopt a greedy strategy to incrementally select $10$ features that maximize our target ${\bf I}({\bf S}_{sub};{\bf Y})$. That is, in each step, we fix the current subset ${\bf S}_{sub} = \{{\bf X}_{i_1}, \cdots, {\bf X}_{i_{l-1}}\}$ and add a new feature ${\bf X}_{i_l} \in {\bf S} / {\bf S}_{sub}$ to ${\bf S}_{sub}$. The average rank of each method across different number of features and the running time of MRMI and LRMI are reported in Table \ref{tbl_selection} and Table \ref{tbl_dataset}.

\begin{table}[t]
	\centering
	\small
	\setlength{\tabcolsep}{0.45em}
	\begin{tabular}{ cccccr@{\hspace{4pt}/\hspace{4pt}}lc }
		\toprule
		Dataset & \#I & \#F & \#C & Discrete & \multicolumn{2}{c}{Time} & Speedup \\
		\midrule
		Breast & 569 & 30 & 2 & No & 0.31 & 0.25 & 1.2 \\
		Semeion & 1593 & 256 & 10 & Yes & 56 & 44 & 1.3 \\
		Madelon & 2600 & 500 & 2 & Yes & 570 & 39 & 14.4 \\
		Krvskp & 3196 & 36 & 2 & Yes & 71 & 11 & 6.6 \\
		Spambase & 4601 & 56 & 2 & No & 353 & 13 & 27.2 \\
		Waveform & 5000 & 40 & 3 & No & 318 & 14 & 22.5 \\
		Optdigits & 5620 & 64 & 10 & Yes & 750 & 41 & 18.4 \\
		Statlog & 6435 & 36 & 6 & Yes & 600 & 23 & 25.7 \\
		\bottomrule
	\end{tabular}
	\caption{Number of instances (\#I), features (\#F), classes (\#C) and discreteness of classification datasets used in feature selection experiments, running time comparison (minutes) of MRMI (left) and LRMI (right), and speedup ratios.}
	\label{tbl_dataset}
\end{table}

As we can see, both  MRMI and LRMI significantly outperform other Shannon entropy based methods. Compared to MRMI, LRMI achieves $6$ to $27$ times speedup, $15$ times on average via Lanczos approximation. Furthermore, LRMI outperforms MRMI on $4$ datasets in our test benchmark, which verifies our theoretical analysis that low-rank R\'enyi's entropy enables higher robustness against noises in the data. This demonstrates the great potential of our low-rank R\'enyi's entropy on information-related tasks.

\section{Conclusion}
In this paper, we investigate an alternative entropy measure built upon the largest $k$ eigenvalues of the data kernel matrix. Compared to the original matrix-based R\'enyi's entropy, our definition enables higher robustness to noises in the data and sensitivity to informative changes in eigenspectrum distribution with a proper choice of hyper-parameter $k$. Moreover, low-rank R\'enyi's entropy can be efficiently approximated with $\mathcal{O}(ns^2)$ random projection and $\mathcal{O}(n^2s)$ Lanczos iteration techniques, substantially lower than the $\mathcal{O}(n^3)$ complexity required to compute matrix-based R\'enyi's entropy. We conduct large-scale simulation and real-world experiments on information bottleneck and feature selection tasks to validate the effectiveness of low-rank R\'enyi's entropy, demonstrating elegant performance with significant improvements in computational efficiency.

\section{Acknowledgments}
This work was supported by National Key Research and Development Program of China (2021ZD0110700), National Natural Science Foundation of China (62106191, 12071166, 62192781, 61721002), the Research Council of Norway (RCN) under grant 309439, Innovation Research Team of Ministry of Education (IRT\_17R86), Project of China Knowledge Centre for Engineering Science and Technology and Project of Chinese Academy of Engineering (The Online and Offline Mixed Educational Service System for The Belt and Road Training in MOOC China).

\section{Supplementary Experimental Results}

\subsection{Parameter Settings of Robustness Experiment}
In the first simulation study, we set $n = 100$, $d = 400$, $\varepsilon = 1/n = 0.01$ and use the linear kernel $\kappa({\bf x}_i, {\bf x}_j) = {\bf x}_i^\top{\bf x}_j$ to generate the kernel matrices. The data samples $\{{\bf x}_i\}_{i=1}^n$ are generated by i.i.d Gaussian distribution $N(0, 0.1^2)$. The noise distributions $\mathcal{E}$ are selected following the criterion that ${\bf E}[\mathcal{E}] = 0$ and ${\bf Var}[\mathcal{E}] = 1$. It can be seen that we get similar results under different noise settings, which further verifies our analysis that when $\varepsilon$ is small, the variance of ${\bf S}_\alpha^k({\bf A})$ mainly depends on the variance of random perturbations of data samples.

\subsection{Additional Results of Approximation Algorithms}
Additionally, we evaluate the impact of $\alpha$ and $c$ on approximation accuracy. We keep the previous $n = 8192$ parameter settings and set $k = 64$. The results of MRE curves with $c = 1.0$ and varying $\alpha$ are reported in Figure \ref{AlphaExp}. For SGS, we set the sparsity hyper-parameter $p=2$. For Lanczos, we randomly select the initial vector ${\bf q}$ from standard Gaussian. It can be seen that GRP achieves the lowest MRE amongst all random projection algorithms. When $\alpha$ is small, all MRE curves exhibit similar behavior and grow with the increase of $\alpha$. This behavior starts to differ when $\alpha$ gets larger. For random projection algorithms, MRE keeps at the same level; for Lanczos algorithm, MRE starts to decrease when $\alpha > 2$. Recall that the larger eigenvalues of ${\bf A}$ take the main role in the calculation of ${\bf S}_\alpha^k({\bf A})$ for large $\alpha$, this phenomenon indicates that Lanczos algorithm achieves higher precision for larger eigenvalues than smaller ones (as shown in our proof, it requires only $\mathcal{O}(i+\log(1/\epsilon))$ steps to approximate $\lambda_i$ to relative error $1\pm\epsilon$), while random projection achieves similar level of precision for all of the $k$ eigenvalues.

We then evaluate the impact of EDR (c) on approximation accuracy. In Figure \ref{DecayExp}, we report the MRE curves for $\alpha = 2$ while $c$ varies from $0$ (flat) to $2$ (steep). It is interesting that the behavior of the two types of methods is entirely different. For random projections, the MRE curves grow slowly (GRP) or keep unchanged (SRHT, IST and SGS) when $c$ is small, and start to increase at a constant rate when $c$ gets large. This is because ${\bf S}_\alpha^k({\bf A})$ is decreasing along with the increase of $c$, whose slope is low at first and high when $c$ gets large (see Figure \ref{fig_intuitive1}). This results in the slow to fast increasing behavior in relative error since the absolute error is upper bounded (Theorem \ref{th:rp_approx}). For Lanczos method, the ratio $\lambda_1/\lambda_r$ in Theorem \ref{th:lanczos_approx} increases fast when $c$ is small, resulting in the increase of MRE. When $c$ gets large, $\lambda_1$ gradually reaches its upper bound $\lambda_1 \le 1$, while the intervals between adjacent eigenvalues also increase and result in a higher $R$ (Theorem \ref{th:lanczos_approx}). Moreover, recall that Lanczos algorithm approximates larger eigenvalues to higher precision, these reasons together explain the increase and then decrease MRE of the Lanczos approach.

Next, we conduct large-scale experiments to evaluate the approximation algorithms. The kernel matrices are generated by ${\bf A} = \bm{\Phi}\bm{\Sigma}\bm{\Phi}^\top$, where $\bm{\Phi} \in \mathbb{R}^{n \times n}$ is a random orthogonal matrix, $\bm{\Sigma} \in \mathbb{R}^{n \times n}$ is a diagonal matrix such that $\bm{\Sigma}_{ii} = i^{-c}$ for $i \in [1,n]$, and $c$ is a constant that controls the EDR. We set size of the kernel matrix $n = 8192$. For random projection methods, we make $s$ vary from $100$ to $1000$; while for Lanczos algorithm, $s$ varies from $64$ to $110$. The mean relative error (MRE) and $\pm\frac{1}{4}$ standard deviation (SD) are reported in Figure \ref{SExp} for each test after $100$ trials with $\alpha = 1.5$ and $c \in \{1.5, 1.0, 0.5\}$, which correspond to high, medium and low EDR respectively. For comparison, the trivial eigenvalue decomposition approach requires $134$ seconds. It can be seen that all random projection methods yield similar approximation accuracy, in which GRP achieves slightly lower MRE when $c = 0.5$ while IST \& SGS bring the highest speedup. The Lanczos method achieves the highest accuracy with significantly lower $s$ values but requires longer running time. Generally, we recommend IST or SGS for medium precision approximation, and Lanczos when high precision is required. These methods achieve more than $25$ times speedup compared to the trivial approach for an $8192 \times 8192$ kernel matrix.

\subsection{Additional Results of Feature Selection}
The hyper-parameter selection result of $\alpha$ and $k$ for matrix-based R\'enyi's entropy and low-rank R\'enyi's entropy in feature selection experiment via cross-validation are shown in Table \ref{tbl_hyper}. As can be seen, $k = 100$ is already suitable for most circumstances. We perform a Nemenyi's post-hoc test \cite{demvsar2006statistical} to give the significant level, in which the confidence that method $i$ significantly outperforms method $j$ is calculated as:
\begin{equation*}
	p_{ij} = \bm{\Phi}\prn*{\left.(R_j - R_i) \middle/ \sqrt{\frac{M(M+1)}{6N}}\right.},
\end{equation*}
where $\bm{\Phi}$ is the CDF of standard normal distribution, $R_i$ is the average rank of method $i$, $M$ is the number of methods and $N$ is the number of datasets. For our case, we have $M = 8$, $N = 8$ and the value of $R_i$ are given in the last column of table \ref{tbl_selection}. The confidence level of different methods is shown in Figure \ref{fig_confidence}. It can be seen that under significance level $p = 0.05$, LRMI significantly outperforms all Shannon's entropy-based methods, while the confidence of MRMI outperforming CMIM is not significant enough. In Figure \ref{fig_selection}, we report the classification accuracy achieved by different feature selection methods for the first $10$ features. It can be seen that classification error tends to stabilize after selecting the $10$ most informative features.

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.4\textwidth]{results/alpha.pdf}
	\caption{$\alpha$ versus MRE curves for entropy approximation.}
	\label{AlphaExp}
\end{figure}

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.4\textwidth]{results/decay.pdf}
	\caption{$c$ versus MRE curves for entropy approximation.}
	\label{DecayExp}
\end{figure}

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.45\textwidth]{results/eigendecay.pdf}
	\caption{$s$ versus MRE curves for entropy approximation. The first three sub-figure correspond to different $c$ values, while the last sub-figure show the running time.}
	\label{SExp}
\end{figure}

\begin{table}[ht]
	\centering
	\begin{tabular}{ ccc }
		\toprule
		Dataset & $\alpha$ & $k$ \\
		\midrule
		Breast & 2.0 & 100 \\
		Semeion & 1.01 & 400 \\
		Madelon & 2.0 & 100 \\
		Krvskp & 1.01 & 200 \\
		Spambase & 2.0 & 100 \\
		Waveform & 2.0 & 100 \\
		Optdigits & 1.01 & 200 \\
		Statlog & 0.6 & 100 \\
		\bottomrule
	\end{tabular}
	\caption{Hyper-parameter selection results of $\alpha$ and $k$ in feature selection experiment.}
	\label{tbl_hyper}
\end{table}

\begin{figure}[t]
	\small
	\centering
	\includegraphics[width=0.3\textwidth]{results/confidence.pdf}
	\caption{Confidence of significant outperforming (\%) for different feature selection methods.}
	\label{fig_confidence}
\end{figure}

\begin{figure*}[t]
	\small
	\centering
	\includegraphics[width=0.9\textwidth]{results/feature.pdf}
	\caption{Number of Features ($l$) versus Classification Error (\%) curves for different feature selection methods.}
	\label{fig_selection}
\end{figure*}

\section{Proof of Main Results}
\subsection{Proof of Proposition \ref{prop_lowrank}}
\begin{proof}
	For (a): Let ${\bf A} = {\bf U}\bm{\Lambda}{\bf U}^\top$ be the eigenvalue decomposition of ${\bf A}$, then ${\bf P}{\bf U}$ is a unitary matrix and $\lambda_i({\bf A}) = \lambda_i({\bf P}{\bf A}{\bf P}^\top)$ for all $i \in [1,k]$.

	For (b): When $p > 0$, ${\bf tr}\prn*{(pL_k({\bf A}))^\alpha} = p^\alpha \cdot {\bf tr}(L_k^\alpha({\bf A})) > 0$, then (b) follows by the continuity of the logarithm function.

	For (c): Notice that ${\bf S}_\alpha^k({\bf A}) = {\bf S}_\alpha(L_k({\bf A}))$, where ${\bf tr}(L_k({\bf A})) = 1$ and $\lambda_i(L_k({\bf A})) \in [0,1]$ for all $i \in [1,n]$. Then we have ${\bf tr}(L_k^\alpha({\bf A})) \ge 1$ when $\alpha \in (0, 1)$ and ${\bf tr}(L_k^\alpha({\bf A})) \le 1$ when $\alpha > 1$, which further implies that ${\bf S}_\alpha^k({\bf A}) \ge 0$.

	Let $f(x) = x^\alpha$, it is obvious that $f$ is concave when $\alpha \in (0,1)$ and convex when $\alpha > 1$. Then by Jensen's inequality, ${\bf tr}(f(L_k({\bf A}))) \le {\bf tr}(f(\frac{1}{n}I))$ when $\alpha \in (0,1)$ and otherwise the opposite, which further implies that ${\bf S}_\alpha^k({\bf A}) \le {\bf S}_\alpha^k(\frac{1}{n}I)$.

	Moreover, it is straightforward to show that ${\bf S}_\alpha^k(\frac{1}{n}I) = {\bf S}_\alpha(\frac{1}{n}I) = \log_2(n)$.

	For (d): From Proposition 4.1 in \cite{giraldo2014measures} we have that ${\bf S}_\alpha({\bf A} \otimes {\bf B}) = {\bf S}_\alpha({\bf A}) + {\bf S}_\alpha({\bf B})$, therefore ${\bf S}_\alpha(L_k({\bf A}) \otimes L_k({\bf B})) = {\bf S}_\alpha(L_k({\bf A})) + {\bf S}_\alpha(L_k({\bf B}))$. Notice that the smaller $(n-k)^2$ eigenvalues of $L_k({\bf A}) \otimes L_k({\bf B})$ are equal to $\lambda_r({\bf A})\lambda_r({\bf B})$, we have ${\bf S}_\alpha^{n^2-(n-k)^2}(L_k({\bf A}) \otimes L_k({\bf B})) = {\bf S}_\alpha^k(L_k({\bf A})) + {\bf S}_\alpha^k(L_k({\bf B}))$.

	For (e): From Proposition 4.1 in \cite{giraldo2014measures} we have that ${\bf S}_\alpha(t{\bf A}_k + (1-t){\bf B}_k) = g^{-1}\big(tg({\bf S}_\alpha({\bf A})) + (1-t)g({\bf S}_\alpha({\bf B}))\big)$. Notice that ${\bf A}_k = {\bf A}$ when ${\bf tr}({\bf A}_k) = 1$, we have ${\bf S}_\alpha^k(t{\bf A} + (1-t){\bf B}) = g^{-1}\big(tg({\bf S}_\alpha^k({\bf A})) + (1-t)g({\bf S}_\alpha^k({\bf B}))\big)$.

	For (f): From the proof of Proposition 4.1 in \cite{giraldo2014measures} we have that
	\begin{equation*}
		\sum_{i=1}^t \lambda_i({\bf A}\circ{\bf B}) \le \frac{1}{n}\sum_{i=1}^t \lambda_i({\bf B}),
	\end{equation*}
	where $t$ is any integer in $[1,n]$. Therefore
	\begin{align*}
		\sum_{i=1}^t \lambda_i(L_k({\bf A}\circ{\bf B})) &\le \frac{1}{n}\sum_{i=1}^t \lambda_i(L_k({\bf B})),\quad \forall t \in [1,k], \\
		\sum_{i=1}^n \lambda_i(L_k({\bf A}\circ{\bf B})) &= \frac{1}{n}\sum_{i=1}^n \lambda_i(L_k({\bf B})) = \frac{1}{n},
	\end{align*}
	From the case $t = k$ we know that $\lambda_r({\bf A}\circ{\bf B}) \ge \lambda_r({\bf B})/n$, therefore for any $t \in [k + 1, n]$, we have
	\begin{align*}
		\sum_{i=1}^t \lambda_i(L_k({\bf A}\circ{\bf B})) &= \frac{1}{n} - (n-t)\lambda_r({\bf A}\circ{\bf B}) \\
		&\le \frac{1}{n} - \frac{n-t}{n}\lambda_r({\bf B}) \\
		&= \frac{1}{n}\sum_{i=1}^t \lambda_i(L_k({\bf B})).
	\end{align*}
	Then we can prove that
	\begin{align*}
		{\bf S}_\alpha^k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}} &= {\bf S}_\alpha\prn*{L_k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}}}\\
		&\ge {\bf S}_\alpha(L_k({\bf B})) = {\bf S}_\alpha^k({\bf B})
	\end{align*}
	following the proof in \cite{giraldo2014measures}.

	For (g): From the proof of Proposition 4.1 in \cite{giraldo2014measures}, when ${\bf A} = \frac{1}{n}\mathbf{1}\1^\top$ and ${\bf A} = \frac{1}{n}I$, we have
	\begin{align*}
		\sum_{i=1}^t \lambda_i({\bf A}\circ{\bf B}) &\le \frac{1}{n}\sum_{i=1}^t \lambda_i({\bf B})\quad \mathrm{and} \\
		\frac{1}{n}\sum_{i=1}^t \lambda_i({\bf A}\circ{\bf B}) &\le \frac{1}{n}\sum_{i=1}^t \lambda_i({\bf B})
	\end{align*}
	respectively, where $t$ is any integer in $[1,n]$. Similar with the proof of (f), for these two extreme cases we can prove that
	\begin{align*}
		\sum_{i=1}^t \lambda_i(L_k({\bf A}\circ{\bf B})) &\le \frac{1}{n}\sum_{i=1}^t \lambda_i(L_k({\bf B}))\quad \mathrm{and} \\
		\frac{1}{n}\sum_{i=1}^t \lambda_i(L_k({\bf A}\circ{\bf B})) &\le \frac{1}{n}\sum_{i=1}^t \lambda_i(L_k({\bf B}))
	\end{align*}
	respectively. These inequalities imply that
	\begin{equation*}
		{\bf S}_\alpha\prn*{L_k\prn*{\frac{{\bf A}\circ{\bf B}}{{\bf tr}({\bf A}\circ{\bf B})}}} \le {\bf S}_\alpha(L_k({\bf A})) + {\bf S}_\alpha(L_k({\bf B}))
	\end{equation*}
	following the proof in \cite{giraldo2014measures}.
\end{proof}

\subsection{Proof of Theorem \ref{th:robust}}
\begin{proof}
	Without loss of generality, we assume $\mu_1 \ge \mu_2 \ge \cdots \ge \mu_n$. Note that $\lambda_i$, $i \in [1,n]$ may not be monotonically decreasing. By the definition of information potential, we have
	\begin{gather*}
		{\bf IP}_\alpha({\bf B}) = \sum_{i=1}^n \mu_i^\alpha, \\
		{\bf IP}_\alpha^k({\bf B}) = \sum_{i=1}^k \mu_i^\alpha + (n-k) \mu_r^\alpha, \\
		\mu_r = \frac{1}{n-k}\prn*{1 - \sum_{i=1}^k \mu_i}.
	\end{gather*}
	When $\nu_i$ is small, we have the following first-order approximation:
	\begin{align*}
		\mu_i^\alpha &= (\lambda_i+\nu_i)^\alpha \\
		&= \lambda_i^\alpha + \alpha\lambda_i^{\alpha-1}\nu_i + \frac{\alpha(\alpha-1)}{2}\lambda_i^{\alpha-2}\nu_i^2 + \cdots \\
		&= \lambda_i^\alpha + \alpha\lambda_i^{\alpha-1}\nu_i + o(\nu_i).
	\end{align*}
	Therefore
	\begin{align*}
		{\bf Var}[{\bf IP}_\alpha({\bf B})] &= {\bf Var}[{\bf IP}_\alpha({\bf B}) - {\bf IP}_\alpha({\bf A})] \\
		&= {\bf Var}\brk*{\sum_{i=1}^n \mu_i^\alpha - \lambda_i^\alpha} \\
		&= {\bf Var}\brk*{\sum_{i=1}^n \alpha\lambda_i^{\alpha-1}\nu_i + o(\nu_i)} \\
		&\approx \alpha^2\sum_{i=1}^n {\bf Var}\brk*{\lambda_i^{\alpha-1}\nu_i} \\
		&= \alpha^2\sum_{i=1}^n \sigma_i^2\lambda_i^{2(\alpha-1)}.
	\end{align*}
	Similarly, we have
	\begin{align*}
		{\bf Var}[{\bf IP}_\alpha^k({\bf B})] &= {\bf Var}[{\bf IP}_\alpha^k({\bf B}) - {\bf IP}_\alpha^k({\bf A})] \\
		&= {\bf Var}\brk*{\sum_{i=1}^k \prn*{\mu_i^\alpha - \lambda_i^\alpha} + (n-k)(\mu_r^\alpha - \lambda_r^\alpha)} \\
		&= {\bf Var}\Bigg[\sum_{i=1}^k \prn*{\alpha\lambda_i^{\alpha-1}\nu_i + o(\nu_i)} \\
		&\qquad - \alpha(n-k)\lambda_r^{\alpha-1}\cdot \frac{1}{n-k}\sum_{i=1}^k \nu_i \Bigg].
	\end{align*}
	When $\alpha \in (0, 1)$, i.e. $\alpha-1 < 0$, we have $\lambda_r^{\alpha-1} \ge \lambda_i^{\alpha-1}$ for $i \in [1, k]$. Therefore
	\begin{align}
		{\bf Var}[{\bf IP}_\alpha^k({\bf B})] &\le {\bf Var}\brk*{\alpha\lambda_r^{\alpha-1}\sum_{i=1}^k \nu_i} \nonumber\\
		&= \alpha^2\lambda_r^{2(\alpha-1)}\sum_{i=1}^k\sigma_i^2 \nonumber\\
		&\le \alpha^2\sum_{i=k+1}^n \sigma_i^2\lambda_i^{2(\alpha-1)} \frac{\sum_{i=1}^k\sigma_i^2}{\sum_{i=k+1}^n\sigma_i^2} \label{eq:jensen}\\
		&\le {\bf Var}[{\bf IP}_\alpha({\bf B})]. \nonumber
	\end{align}
	(\ref{eq:jensen}) follows by Jensen's inequality using the fact that $\lambda_r = \frac{1}{n-k} \sum_{i=k+1}^n \lambda_i$ and $\sigma_i$ are non-negative, since the function $f(x) = x^{2(\alpha-1)}$ is convex.

	Otherwise when $\alpha > 1$, we have $\lambda_r^{\alpha-1} \le \lambda_i^{\alpha-1}$ for $i \in [1, k]$. Therefore
	\begin{align*}
		{\bf Var}[{\bf IP}_\alpha^k({\bf B})] &\le {\bf Var}\brk*{\alpha\sum_{i=1}^k \lambda_i^{\alpha-1}\nu_i} \\
		&= \alpha^2\sum_{i=1}^k\sigma_i^2\lambda_i^{2(\alpha-1)} \\
		&\le {\bf Var}[{\bf IP}_\alpha({\bf B})].
	\end{align*}
	This completes the proof.
\end{proof}

\subsection{Uniqueness of Low-rank R\'enyi's Entropy}
Let ${\bf S}_\alpha^k({\bf A})$ be a measure of entropy defined on the largest $k$ eigenvalues of ${\bf A}$. Then ${\bf S}_\alpha^k({\bf A})$ must adopt some strategy to build a probability distribution upon known eigenvalues, i.e. let the summation of all eigenvalues be exactly $1$, otherwise ${\bf S}_\alpha^k({\bf A})$ will not be continuous at $\alpha=1$. One choice is to adopt some strategy to complement the missing eigenvalues. Let $L_k({\bf A})$ be the complemented matrix, we have $\lambda_i(L_k({\bf A})) = \lambda_i({\bf A}), \forall i \in [1,k]$, $\lambda_n(L_k({\bf A})) \le \cdots \le \lambda_{k+1}(L_k({\bf A})) \le \lambda_k({\bf A})$ and ${\bf tr}(L_k({\bf A})) = 1$.

Let $F_{\bf A}(t)$ be the CDF of ${\bf A}$: $F_{\bf A}(t) = \sum_{i=1}^t \lambda_i({\bf A})$, and let $\lambda_r({\bf A}) = \frac{1}{n-k}(1 - \sum_{i=1}^k \lambda_i({\bf A}))$. Then we have
\begin{equation} \label{eq_unique_lower}
	F_{L_k({\bf A})}(t) \ge \sum_{i=1}^k \lambda_i({\bf A}) + (t-k) \lambda_r({\bf A})
\end{equation}
for all $t \in [k+1,n]$ since the function $F_{\bf A}$ is always concave. Let ${\bf B} \in \mathbb{R}^{n \times n}$ be a PSD matrix satisfying
\begin{equation*}
	\sum_{i=1}^t \lambda_i({\bf A}) \le \sum_{i=1}^t \lambda_i({\bf B})
\end{equation*}
for all $t \in [1,n]$, then in order to maintain the triangle inequality (axiom (f) and (g)), The function $F_{\bf A}$ must satisfy $F_{L_k({\bf A})}(t) \le F_{L_k({\bf B})}(t)$, $\forall t \in [k+1,n]$. Construct ${\bf B}$ by letting $\lambda_1({\bf B}) = 1 - (n-1)\lambda_r({\bf A})$ and $\lambda_2({\bf B}) = \cdots = \lambda_n({\bf B}) = \lambda_r({\bf A})$, then combining with the fact that $\lambda_i(L_k({\bf B})) \le \lambda_k({\bf B})$, $\forall i \in [k+1,n]$, we have
\begin{equation} \label{eq_unique_upper}
	F_{L_k({\bf A})}(t) \le F_{L_k({\bf B})}(t) = \sum_{i=1}^k \lambda_i({\bf A}) + (t-k) \lambda_r({\bf A}).
\end{equation}
Eq. (\ref{eq_unique_lower}) and (\ref{eq_unique_upper}) together imply that taking $\lambda_i(L_k({\bf A})) = \lambda_r({\bf A})$ for all $i \in [k+1,n]$ is the only choice that fulfills all axioms in Proposition \ref{prop_lowrank}.

Another reasonable choice to normalize the probability distribution is to scale the known largest $k$ eigenvalues:
\begin{equation*}
	{\bf S}_\alpha^k({\bf A}) = \frac{1}{1-\alpha}\log_2 \prn*{\sum_{i=1}^k \prn*{\frac{\lambda_i({\bf A})}{\sum_{i=1}^n \lambda_i({\bf A})}}^\alpha},
\end{equation*}
or
\begin{equation*}
	{\bf S}_\alpha^k({\bf A}) = \frac{1}{1-\alpha}\log_2 \prn*{\frac{\sum_{i=1}^k \lambda_i^\alpha({\bf A})}{\sum_{i=1}^n \lambda_i({\bf A})}}.
\end{equation*}
However, these methods do not fulfill the triangle inequality, i.e. we cannot infer ${\bf S}_\alpha^k({\bf A}) \ge {\bf S}_\alpha^k({\bf B})$ from the condition that $F_{{\bf A}}(t) \le F_{{\bf B}}(t)$, $\forall t \in [1,k]$. This results in violations of axioms (f) and (g).

\subsection{Proof of Theorem \ref{th:rp_approx}}
We first present the $\ell_2$ embedding results for RGP, SRHT, IST and SGS in Lemma \ref{lemma_RGP}, \ref{lemma_hadamard}, \ref{lemma_sparse} and \ref{lemma_bipartite} respectively, where the dimension of embedding subspace is given to guarantee the $\epsilon$ error. Lemma \ref{lemma_permutation} presents the permutation bound for symmetric positive definite matrix. All these theoretical results are helpful to our proof.
\begin{lemma} \label{lemma_RGP}
	\cite{foucart13} Let ${\bf U} \in \mathbb{R}^{n \times k } $ such that ${\bf U}^\top {\bf U} = {\bf I}_k$ and ${\bf P} \in \mathbb{R}^{n \times s}$ constructed by GRP. Then, with probability at least  $1 - \delta$,
	\begin{equation*}
		\left\|   {\bf U}^\top {\bf P} {\bf P}^\top {\bf U} - {\bf I}_k \right\|_2 \leq \epsilon,
	\end{equation*}
	by setting $s = \mathcal{O} \left(  k + \log(1/\delta) /\epsilon^2 \right)$.
\end{lemma}

\begin{lemma} \label{lemma_hadamard}
	\cite{drineas2012fast} 	Let ${\bf U} \in \mathbb{R}^{n \times k } $ such that ${\bf U}^\top {\bf U} = {\bf I}_k$ and ${\bf P} \in \mathbb{R}^{n \times s}$ constructed by SRHT. Then, with probability at least 0.9,
	\begin{equation*}
		\left\|  \frac{n}{k} {\bf U}^\top {\bf P} {\bf P}^\top {\bf U} - {\bf I}_k \right\|_2 \leq \epsilon,
	\end{equation*}
	by setting $s = \mathcal{O} \left( (k+ \log n) \frac{\log k}{\epsilon^2}\right)$.
\end{lemma}

\begin{lemma} \label{lemma_sparse}
	\cite{woodruff2014sketch} Let ${\bf U} \in \mathbb{R}^{n \times k } $ such that ${\bf U}^\top {\bf U} = {\bf I}_k$ and ${\bf P} \in \mathbb{R}^{n \times s}$ constructed by IST. Then, with probability at least 0.9,
	\begin{equation*}
		\left\|   {\bf U}^\top {\bf P} {\bf P}^\top {\bf U} - {\bf I}_k \right\|_2 \leq \epsilon,
	\end{equation*}
	by setting $s = \mathcal{O} \left(  k^2 /\epsilon^2 \right)$.
\end{lemma}

\begin{lemma} \label{lemma_bipartite}
	\cite{hu2021sparse} Let ${\bf U} \in \mathbb{R}^{n \times k } $ such that ${\bf U}^\top {\bf U} = {\bf I}_k$ and ${\bf P} \in \mathbb{R}^{n \times s}$ constructed by SGS. Then, with probability at least $1 - \delta$,
	\begin{equation*}
		\left\|   {\bf U}^\top {\bf P} {\bf P}^\top {\bf U} - {\bf I}_k \right\|_2 \leq \epsilon,
	\end{equation*}
	by setting
	\begin{align*}
		s &= \mathcal{O} \left(k\log(k/\delta\epsilon)/\epsilon^2 \right), \\
		p &= \mathcal{O} \left(\log(k/\delta\epsilon) /\epsilon \right).
	\end{align*}
\end{lemma}

\begin{lemma} \label{lemma_permutation}
	\cite{demmel1992jacobi}	Let ${\bf D} {\bf G} {\bf D}$ be a symmetric positive definite matrix such that ${\bf D}$ is a diagonal matrix and ${\bf G}_{ii}= 1$ for all $i$. Let ${\bf D} {\bf E} {\bf D}$ be a permutation matrix such that $\| {\bf E}\|_2 < \lambda_{\min}({\bf G})$. Let $\lambda_i$ be the $i$-th eigenvalue of ${\bf D} {\bf G} {\bf D}$ and $\hat{\lambda}_i$ be the $i$-th eigenvalue of ${\bf D}({\bf G}+{\bf E}){\bf D}$. Then, for all $i$,
	\begin{equation*}
		|\lambda_i - \hat{\lambda}_i| \leq \frac{\| {\bf E}\|_2}{\lambda_{\min}({\bf G})}.
	\end{equation*}
\end{lemma}

The following proposition shows that if we can bound each eigenvalue of ${\bf A}$ to absolute error $\epsilon$, we have an absolute bound for ${\bf S}_\alpha({\bf A})$.

\begin{proposition} \label{prop_renyi_bound}
	Let ${\bf A}$ and $\hat{{\bf A}}$ be positive definite matrices with eigenvalues $\lambda_i$ and $\hat{\lambda}_i$, $i \in [1,n]$ respectively, such that for each $i \in [1,n]$, $\abs{\lambda_i - \hat{\lambda}_i} \le \epsilon$, then
	\begin{equation*}
		\abs{{\bf S}_\alpha({\bf A}) - {\bf S}_\alpha(\hat{{\bf A}})} \le \abs*{\frac{\alpha}{1-\alpha} \log_2 \prn*{1-\frac{\epsilon}{\lambda_n}}}.
	\end{equation*}
\end{proposition}
\begin{proof}
	Let $\lambda_n > 0$ be the smallest eigenvalue of ${\bf A}$ and let $\epsilon_0 = \epsilon/\lambda_n$, then we have $\abs{\lambda_i - \hat{\lambda}_i} \le \epsilon_0 \lambda_i$ for each $i \in [1,n]$. Observe that when $\alpha < 1$,
	\begin{align*}
		{\bf S}_\alpha(\hat{{\bf A}}) &= \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^n \hat{\lambda}_i^\alpha} \\
		&\ge \frac{1}{1-\alpha} \log_2 \prn*{(1-\epsilon_0)^\alpha \sum_{i=1}^n \lambda_i^\alpha} \\
		&= \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^n \lambda_i^\alpha} + \frac{\alpha}{1-\alpha} \log_2(1-\epsilon_0) \\
		&= {\bf S}_\alpha({\bf A}) + \frac{\alpha}{1-\alpha} \log_2(1-\epsilon_0).
	\end{align*}
	Similarly, we have
	\begin{align*}
		{\bf S}_\alpha(\hat{{\bf A}}) &= \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^n \hat{\lambda}_i^\alpha} \\
		&\le \frac{1}{1-\alpha} \log_2 \prn*{(1+\epsilon_0)^\alpha \sum_{i=1}^n \lambda_i^\alpha} \\
		&= \frac{1}{1-\alpha} \log_2 \prn*{\sum_{i=1}^n \lambda_i^\alpha} + \frac{\alpha}{1-\alpha} \log_2(1+\epsilon_0) \\
		&= {\bf S}_\alpha({\bf A}) + \frac{\alpha}{1-\alpha} \log_2(1+\epsilon_0).
	\end{align*}
	We can get the same results for the other case when $\alpha > 1$, which finishes the proof.
\end{proof}

\begin{proof}[Proof of Theorem \ref{th:rp_approx}]
	Note that $\lambda_{\min}({\bf G})$ in the Lemma \ref{lemma_permutation} is a real, strictly positive number since ${\bf G}$ is positive definite and the fact $0 \leq \|E\|_2  \lambda_{\min}({\bf G})$. Now consider the matrix ${\bf A} {\bf P} {\bf P}^\top {\bf A}^\top$, we will show that the singular values of ${\bf A} {\bf P} {\bf P}^\top {\bf A}$ are sufficient approximation to that of  ${\bf A} {\bf A}^\top$ by the permutation theory presented in Lemma \ref{lemma_permutation}.

	Let $\lambda_i$, $i \in [1,n]$ be the eigenvalues of the positive definite kernel matrix ${\bf A}$, $\hat{\lambda}_i$ be their approximations and ${\bf A} = \bm{\Phi} \bm{\Sigma} \bm{\Phi}^\top$ be the eigenvalue decomposition ${\bf A}$. Since $\bm{\Phi}$ is an orthogonal matrix, we have that the eigenvalues of $\bm{\Phi} \bm{\Sigma} \bm{\Phi}^\top {\bf P} {\bf P}^\top \bm{\Phi} \bm{\Sigma} \bm{\Phi}^\top$ are equal to the eigenvalues of $\bm{\Sigma} \bm{\Phi}^\top {\bf P} {\bf P}^\top \bm{\Phi} \bm{\Sigma}$. Let $\bm{\Sigma}_k$ be the $k \times k$ diagonal matrix containing the $k$ largest eigenvalues of ${\bf A}$ and $\bm{\Phi}_k$ be the matrix containing the corresponding eigenvectors, then $\lambda_i^2$, $i \in [1,k]$ are the eigenvalues of matrix $\bm{\Sigma}_k{\bf I}_k\bm{\Sigma}_k$, and $\hat{\lambda}_i^2$, $i \in [1,k]$ are the eigenvalues of matrix $\bm{\Sigma}_k \bm{\Phi}_k^\top {\bf P} {\bf P}^\top \bm{\Phi}_k \bm{\Sigma}_k$ (since the first $k$ singular values of $\bm{\Sigma}_k \bm{\Phi}_k^\top {\bf P}$ are equal to those of  $\bm{\Phi} \bm{\Sigma} \bm{\Phi}^\top {\bf P} = {\bf A} {\bf P}$). Let ${\bf E} = \bm{\Phi}_k^\top {\bf P} {\bf P}^\top \bm{\Phi}_k - {\bf I}_k$, we know from Lemma \ref{lemma_RGP} (or Lemma \ref{lemma_hadamard}, \ref{lemma_sparse} and \ref{lemma_bipartite}) that $\|{\bf E}\|_2 \leq \epsilon_0$ with high probability. It meets the condition of Lemma \ref{lemma_permutation} since $\lambda_{\min}({\bf I}_k) = 1$. Hence, we have
	\begin{equation*}
		|\lambda_i^2 - \hat{\lambda}_i^2 | \le \epsilon_0, \quad \forall i \in [1,k],
	\end{equation*}
	which then implies that
	\begin{equation*}
		\lambda_i - \sqrt{\lambda_i^2 - \epsilon_0} \le \abs{\hat{\lambda}_i - \lambda_i} \le \sqrt{\lambda_i^2 + \epsilon_0} - \lambda_i.
	\end{equation*}
	Since $\lambda_k$ is the smallest eigenvalue amongst $\lambda_i$, $i \in [1,k]$, we have
	\begin{align*}
		\abs{\hat{\lambda}_i - \lambda_i} &\le \lambda_k - \sqrt{\lambda_k^2 - \epsilon_0} \\
		&= \lambda_k \prn*{1 - \sqrt{1 - \frac{\epsilon_0}{\lambda_k^2}}} \\
		&\le \lambda_k \frac{\epsilon_0}{\lambda_k^2} = \frac{\epsilon_0}{\lambda_k}.
	\end{align*}
	Combining with $k \le n/2$, we have
	\begin{align*}
		\abs{\hat{\lambda}_r - \lambda_r} &= \left.\abs*{\sum_{i=1}^k \hat{\lambda}_i - \sum_{i=1}^k \lambda_i} \middle/ (n-k)\right. \\
		&\le \frac{\epsilon_0}{\lambda_k} \cdot \frac{k}{n-k} \le \frac{\epsilon_0}{\lambda_k}.
	\end{align*}
	Let $\epsilon_0 = \epsilon\lambda_k\lambda_r$ and ${\bf B}$ be a positive definite matrix with the first $k$ eigenvalues equal to $\hat{\lambda}_i$, $i \in [1,k]$ and the other $n-k$ eigenvalues equal to $\hat{\lambda}_r$. Recall that $\lambda_r$ is the smallest eigenvalue of $L_k({\bf A})$, by applying Proposition \ref{prop_renyi_bound}, we have
	\begin{align*}
		\abs{{\bf S}_\alpha^k({\bf A}) - \hat{{\bf S}}_\alpha^k({\bf A})} &= \abs{{\bf S}_\alpha(L_k({\bf A})) - {\bf S}_\alpha({\bf B})} \\
		&\le \abs*{\frac{\alpha}{1-\alpha} \log_2 \prn*{1-\epsilon}}.
	\end{align*}
\end{proof}

\subsection{A Potential Improvement}
The upper bound of $s$ in Theorem \ref{th:rp_approx} relies on $\lambda_r$, which grows large if the kernel matrix ${\bf A}$ is ill-posed and $\lambda_r$ is small. Alternatively, we derive an upper bound for $s$ in terms of $n$ and ${\bf tr}({\bf A}^\alpha)$, which is tighter for such kernel matrices.
\begin{proposition}
	Under the same conditions as Proposition \ref{prop_renyi_bound}, we have
	\begin{equation*}
		\abs{{\bf S}_\alpha({\bf A}) - {\bf S}_\alpha(\hat{{\bf A}})} \le \begin{cases}
			\abs*{\frac{1}{1-\alpha}\log\prn*{1-\frac{n\alpha\epsilon}{1+n\epsilon}}} & \textrm{if } \alpha > 1, \\
			\abs*{\frac{1}{1-\alpha}\log\prn*{1-\frac{n\epsilon^\alpha}{tr(A^\alpha)}}} & \textrm{if } \alpha < 1.
		\end{cases}
	\end{equation*}
\end{proposition}
\begin{proof}
	\begin{align*}
		S_\alpha(\tilde{{\bf A}})-S_\alpha({\bf A}) &= \abs*{\frac{1}{1-\alpha}\log\prn*{1-\frac{\sum_{i=1}^n\hat{\lambda}_i^\alpha - \sum_{i=1}^n\lambda_i^\alpha}{\sum_{i=1}^n\hat{\lambda}_i^\alpha}}} \\
		&\le \abs*{\frac{1}{1-\alpha}\log\prn*{1-\beta}},
	\end{align*}
	where
	\begin{align*}
		\beta &= \abs*{\frac{\sum_{i=1}^n(\lambda_i+\epsilon)^\alpha - \sum_{i=1}^n\lambda_i^\alpha}{\sum_{i=1}^n(\lambda_i+\epsilon)^\alpha}} \\
		&\le \abs*{\frac{\sum_{i=1}^n(\lambda_i+\epsilon)^\alpha - \sum_{i=1}^n\lambda_i^\alpha}{\sum_{i=1}^n\lambda_i^\alpha}}.
	\end{align*}
	When $\alpha > 1$, we have
	\begin{equation*}
		\beta \le \alpha\epsilon\abs*{\frac{\sum_{i=1}^n(\lambda_i+\epsilon)^{\alpha-1}}{\sum_{i=1}^n(\lambda_i+\epsilon)^\alpha}} \le \frac{n\alpha\epsilon}{1+n\epsilon},
	\end{equation*}
	where the last step takes equality if and only if $\lambda_1 = \cdots = \lambda_n = \frac{1}{n}$. Otherwise when $\alpha < 1$,
	\begin{equation*}
		\beta \le \abs*{\frac{\sum_{i=1}^n\epsilon^\alpha}{\sum_{i=1}^n\lambda_i^\alpha}} = \frac{n\epsilon^\alpha}{tr(A^\alpha)}.
	\end{equation*}
	One can upper bound $S_\alpha(A) - S_\alpha(\tilde{A})$ through the same strategy, which finishes the proof.
\end{proof}

\subsection{Proof of Theorem \ref{th:lanczos_approx}}
The following lemma gives the convergence rate of the Lanczos algorithm:
\begin{lemma} \label{lemma_lanczos}
	\cite{saad1980rates} Let ${\bf q}$ be the initial vector, $\lambda_i$ be the $i$-th largest eigenvalue of ${\bf A}$ with associated eigenvector $\bm{\phi}_i$ such that $\ang{\bm{\phi}_i, {\bf q}} \ne 0$, $\hat{\lambda}_i$ be the corresponding approximation of $\lambda_i$ after $s$ steps of Lanczos iteration, and assume that $\hat{\lambda}_{i-1} > \lambda_i$. Let
	\begin{align*}
		\gamma_i &= 1 + 2\frac{\lambda_i - \lambda_{i+1}}{\lambda_{i+1} - \lambda_n}, \\
		K_i &= \begin{cases}
			\prod_{j=1}^{i-1} \frac{\hat{\lambda}_j - \lambda_n}{\hat{\lambda}_j - \lambda_i}, & i > 1 \\
			1, & i = 1
		\end{cases},
	\end{align*}
	then
	\begin{equation*}
		0 \le \lambda_i - \hat{\lambda}_i \le (\lambda_i - \lambda_n) \cdot \prn*{\frac{K_i}{T_{s-i}(\gamma_i)} \tan\ang{\bm{\phi}_i, {\bf q}}}^2,
	\end{equation*}
	where $T_i(x) = \frac{1}{2} \brk*{(x+\sqrt{x^2-1})^i + (x-\sqrt{x^2-1})^i}$ is the Chebyshev polynomial of the first kind of degree $i$.
\end{lemma}

\begin{proof}[Proof of Theorem \ref{th:lanczos_approx}]
	It is easy to see that $K_i$ is monotonically increasing with the increase of $i$. Let
	\begin{align*}
		\gamma &= \min_{i \in [1,k]} \gamma_i, \\
		\theta &= \max_{i \in [1,k]} \tan\ang{\bm{\phi}_i, {\bf q}}, \\
		R &= \gamma + \sqrt{\gamma^2 - 1},
	\end{align*}
	then $\forall i \in [1,k]$,
	\begin{align*}
		\lambda_i - \hat{\lambda}_i &\le \lambda_i \cdot \prn*{\frac{2\theta K_i}{R^{s-i} + R^{-(s-i)}}}^2 \\
		&\le \lambda_i \cdot 4\theta^2K_i^2 R^{-2(s-i)} \\
		&\le \lambda_i \cdot 4\theta^2K_k^2 R^{-2(s-k)}. \\
	\end{align*}
	By selecting $s = \ceil*{k + \frac{\log\prn*{4\theta^2K_k^2/\epsilon_0}}{2\log R}}$, we have that $\forall i \in [1,k]$,
	\begin{equation*}
		\abs{\lambda_i - \hat{\lambda}_i} \le \epsilon_0\lambda_i.
	\end{equation*}
	Similarly, by combining with $k \le n/2$ we have
	\begin{equation*}
		\abs{\hat{\lambda}_r - \lambda_r} \le \epsilon_0\lambda_1.
	\end{equation*}
	Let $\epsilon_0 = \epsilon\lambda_r/\lambda_1$, by applying Proposition \ref{prop_renyi_bound}, we have
	\begin{equation*}
		\abs{{\bf S}_\alpha^k({\bf A}) - \hat{{\bf S}}_\alpha^k({\bf A})} \le \abs*{\frac{\alpha}{1-\alpha} \log_2 \prn*{1-\epsilon}}.
	\end{equation*}
\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
VIDSIG Announces Partnership with National Baseball Hall of Fame
SAN FRANCISCO, July 11, 2019 /PRNewswire/ -- The National Baseball Hall of Fame announced earlier today a unique technology partnership with VIDSIG, Inc., a California-based software company that offers live one-on-one video interactions between athletes and fans. The technology will allow Hall of Fame athletes to hold virtual "meet and greets" or autograph sessions through the use of a computer from the comfort of the athletes' homes.
Founded by Jeff Dudum, Willie McCovey's godson who helped Willie continue to earn much-needed income after he lost the use of his legs in the latter part of his life, VIDSIG has worked with such Hall of Famers as Joe Morgan, Orlando Cepeda, Reggie Jackson, and others outside of the National Baseball Hall of Fame, such as NFL great Joe Montana and NBA legend Chris Mullin.
"We're thrilled to be partnering with VIDSIG to provide Hall of Famers and their fans with a unique and easy way to connect via live video," stated Sean Gahagan, Vice President of Retail Merchandising & Licensing for the National Baseball Hall of Fame. "Wllie's intention was always to 'help the guys' in the Hall of Fame, and we believe strongly that this will provide an effective way to do so."
The mission at VIDSIG is simple - to bridge the gap between fans and their sports heroes by providing a new, easy way to connect. The company's proprietary technology provides an easy-to-use platform for athletes to hold live video chats and autograph signings, all from the comfort of their own home, office, or wherever a computer is accessible.
"To partner with the esteemed National Baseball Hall of Fame and to further my godfather Willie's dream is mind-blowing to me, my family, and to VIDSIG," stated Jeff Dudum, Founder and CEO of VIDSIG. "To see these amazing ballplayers continuing to connect with their fans on our platform and witness the outpouring of emotion that these once-in-a-lifetime interactions create is incredibly humbling, to say the least."
For more information on the National Baseball Hall of Fame, please visit https://baseballhall.org/
To learn more about VIDSIG, visit https://vidsig.com/
Melissa Kress
217744@email4pr.com
View original content to download multimedia:http://www.prnewswire.com/news-releases/vidsig-announces-partnership-with-national-baseball-hall-of-fame-300882865.html
SOURCE VIDSIG


Let's make some money for WCR and St. Jude's!!!!
It's time again for us to start planning our Annual Fashion Show! Rebecca Ball will be the Team Lead this year, and she's looking for a stellar team. We clearly have an impressive group of volunteers based on the amazing success of the Holiday Auction!!
The second meeting will be this Friday, January 26th at 2:00pm at Keller Williams Clients' Choice, near Chapel Hills Mall.
Please attend if you are willing and able. THANKS!!!!


text:
Q: Datamapper upgrade fails in rails 3.1 for 2nd repository I'm trying to use Datamapper in my Rails 3.1 application and I'm having trouble mapping models that exist on a 2nd repository.
I have the following class
class Arp
  include DataMapper::Resource

  storage_names[:passive] = "arp"

  property :id, Serial, :field => "id"
  property :ip_address, String, :field => "ipaddr"

  def self.default_repository_name
    :passive
  end
end

There are some more fields but for the sake of simplicity I commented them out and got the same error. Here's what I get when i run rake db:migrate:

Arp must have at least one property or many to one relationship to be valid

Not sure what's going on because I clearly have a property defined.
Here's the table sttucture from mysql
+--------+-------------+------+-----+---------+----------------+
| Field  | Type        | Null | Key | Default | Extra          |
+--------+-------------+------+-----+---------+----------------+
| id     | int(11)     | NO   | PRI | NULL    | auto_increment |
| ipaddr | varchar(15) | NO   |     | NULL    |                |
+--------+-------------+------+-----+---------+----------------+

Again a few fields removed for clarity.
I have the multiple repositories in my database.yml file in rails and I set them up based on the guide on the dm-rails github page.
Here's a shortened version of that file.
passive_defaults: &passive_defaults
  adapter: mysql
  username: <USERNAME GOES HERE>
  password: <PASSWORD GOES HERE>
  host: localhost
  database: passive

development:
  database: portal
  <<: *portal_defaults
  repositories:
    passive:
      <<: *passive_defaults

Anyone see what I'm doing wrong here? Thanks.

A: I solved this shortly after asking the question.
The order of the self.default_repository_name override mattered. So
class Arp
  include DataMapper::Resource

  def self.default_repository_name
    :passive
  end
  storage_names[:passive] = "arp"

  property :id, Serial, :field => "id"
  property :ip_address, String, :field => "ipaddr"
end

works.

redpajama_set_name: RedPajamaStackExchange