Search

The real anisotropic Littlewood's $4 / 3$ inequality is an extension of a famous result obtained in 1930 by J. E. Littlewood. It asserts that, for $a , b \in ( 0 , \infty )$, the following conditions are equivalent: $\bullet$ There is an optimal constant $\mathsf{L}_{ a , b }^{ \mathbb{R} } \in [ 1 , \infty )$ such that \[ \Biggl ( \, \sum_{ k = 1 }^{ \infty } \biggl ( \, \sum_{ j = 1 }^{ \infty } \bigl \lvert A \bigl ( \boldsymbol{e}^{ (k) } , \boldsymbol{e}^{ (j) } \bigr ) \bigr \rvert^a \biggr )^{ \frac{b}{a} } \Biggr )^{ \frac{1}{b} } \leq \mathsf{L}_{ a , b }^{ \mathbb{R} } \cdot \lVert A \rVert \] for every continuous bilinear form $A \colon c_0 \times c_0 \to \mathbb{R}$. $\bullet$ The values $a , b$ satisfy $a , b \geq 1$ and $\frac{1}{a} + \frac{1}{b} \leq \frac{3}{2}$. Several authors have obtained the values of $\mathsf{L}_{ a , b }^{ \mathbb{R} }$ for diverse pairs $( a , b )$. In this paper we provide the complete list of such optimal values, as well as new estimates for $\mathsf{L}_{ a , b }^{ \mathbb{C} }$ (the analog for continuous $\mathbb{C}$-bilinear forms), which are exact in several cases. As an application we prove, in terms of the values $\mathsf{L}_{ 1 , r }^{ \mathbb{C} }$, a variant of Khinchin's inequality for Steinhaus variables, and we determine all the optimal $( q , s )$-cotype constants of the spaces $\ell_1 ( \mathbb{K} )$ (with $\mathbb{K} = \mathbb{R}$ or $\mathbb{C}$) in terms of the values $\mathsf{L}_{ 1 , q }^{ \mathbb{R} }$., Comment: Corrected typos and improved presentation and formatting. Added the section about cotype

Contrastive learning has emerged as a powerful method in deep learning, excelling at learning effective representations through contrasting samples from different distributions. However, neural collapse, where embeddings converge into a lower-dimensional space, poses a significant challenge, especially in semi-supervised and self-supervised setups. In this paper, we first theoretically analyze the effect of large learning rates on contrastive losses that solely rely on the cosine similarity metric, and derive a theoretical bound to mitigate this collapse. {Building on these insights, we propose CLOP, a novel semi-supervised loss function designed to prevent neural collapse by promoting the formation of orthogonal linear subspaces among class embeddings.} Unlike prior approaches that enforce a simplex ETF structure, CLOP focuses on subspace separation, leading to more distinguishable embeddings. Through extensive experiments on real and synthetic datasets, we demonstrate that CLOP enhances performance, providing greater stability across different learning rates and batch sizes., Comment: 17 pages, 8 figures

Contrastive Learning (CL) has emerged as a powerful method for training feature extraction models using unlabeled data. Recent studies suggest that incorporating a linear projection head post-backbone significantly enhances model performance. In this work, we investigate the use of a transformer model as a projection head within the CL framework, aiming to exploit the transformer's capacity for capturing long-range dependencies across embeddings to further improve performance. Our key contributions are fourfold: First, we introduce a novel application of transformers in the projection head role for contrastive learning, marking the first endeavor of its kind. Second, our experiments reveal a compelling "Deep Fusion" phenomenon where the attention mechanism progressively captures the correct relational dependencies among samples from the same class in deeper layers. Third, we provide a theoretical framework that explains and supports this "Deep Fusion" behavior. Finally, we demonstrate through experimental results that our model achieves superior performance compared to the existing approach of using a feed-forward layer., Comment: 10 pages, 2 figures

In the Subspace Clustering with Missing Data (SCMD) problem, we are given a collection of n partially observed d-dimensional vectors. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of SCMD is to cluster the vectors according to their subspace membership and recover the underlying basis, which can then be used to infer their missing entries. State-of-the-art algorithms for SCMD can fail on instances with a high proportion of missing data, full-rank data, or if the underlying subspaces are similar to each other. We propose a novel integer programming approach for SCMD. The approach is based on dynamically determining a set of candidate subspaces and optimally assigning points to selected subspaces. The problem structure is identical to the classical facility-location problem, with subspaces playing the role of facilities and data points that of customers. We propose a column-generation approach for identifying candidate subspaces combined with a Benders decomposition approach for solving the linear programming relaxation of the formulation. An empirical study demonstrates that the proposed approach can achieve better clustering accuracy than state-of-the-art methods when the data is high-rank, the percentage of missing data is high, or the subspaces are similar., Comment: 31 pages, 8 tables,8 figures

This paper derives a perturbation bound on the optimal subspace estimator obtained from a subset of its canonical projections contaminated by noise. This fundamental result has important implications in matrix completion, subspace clustering, and related problems., Comment: To appear in Proc. of IEEE, ISIT 2022

This paper introduces {\em fusion subspace clustering}, a novel method to learn low-dimensional structures that approximate large scale yet highly incomplete data. The main idea is to assign each datum to a subspace of its own, and minimize the distance between the subspaces of all data, so that subspaces of the same cluster get {\em fused} together. Our method allows low, high, and even full-rank data; it directly accounts for noise, and its sample complexity approaches the information-theoretic limit. In addition, our approach provides a natural model selection {\em clusterpath}, and a direct completion method. We give convergence guarantees, analyze computational complexity, and show through extensive experiments on real and synthetic data that our approach performs comparably to the state-of-the-art with complete data, and dramatically better if data is missing., Comment: Accepted at IJCNN 2022. arXiv admin note: substantial text overlap with arXiv:1808.00628

Computation of confidence sets is central to data science and machine learning, serving as the workhorse of A/B testing and underpinning the operation and analysis of reinforcement learning algorithms. This paper studies the geometry of the minimum-volume confidence sets for the multinomial parameter. When used in place of more standard confidence sets and intervals based on bounds and asymptotic approximation, learning algorithms can exhibit improved sample complexity. Prior work showed the minimum-volume confidence sets are the level-sets of a discontinuous function defined by an exact p-value. While the confidence sets are optimal in that they have minimum average volume, computation of membership of a single point in the set is challenging for problems of modest size. Since the confidence sets are level-sets of discontinuous functions, little is apparent about their geometry. This paper studies the geometry of the minimum volume confidence sets by enumerating and covering the continuous regions of the exact p-value function. This addresses a fundamental question in A/B testing: given two multinomial outcomes, how can one determine if their corresponding minimum volume confidence sets are disjoint? We answer this question in a restricted setting.

Kwapie\'{n}'s theorem asserts that every continuous linear operator from $\ell_{1}$ to $\ell_{p}$ is absolutely $\left( r,1\right) $-summing for $1/r=1-\left\vert 1/p-1/2\right\vert .$ When $p=2$ it recovers the famous Grothendieck's theorem. In this paper investigate multilinear variants of these theorems and related issues. Among other results we present a unified version of Kwapie\'{n}'s and Grothendieck's results that encompasses the cases of multiple summing and absolutely summing multilinear operators., Comment: 10 pages

To protect tropical forest biodiversity, we need to be able to detect it reliably, cheaply, and at scale. Automated species detection from passively recorded soundscapes via machine-learning approaches is a promising technique towards this goal, but it is constrained by the necessity of large training data sets. Using soundscapes from a tropical forest in Borneo and a Convolutional Neural Network model (CNN) created with transfer learning, we investigate i) the minimum viable training data set size for accurate prediction of call types ('sonotypes'), and ii) the extent to which data augmentation can overcome the issue of small training data sets. We found that even relatively high sample sizes (> 80 per call type) lead to mediocre accuracy, which however improves significantly with data augmentation, including at extremely small sample sizes, regardless of taxonomic group or call characteristics. Our results suggest that transfer learning and data augmentation can make the use of CNNs to classify species' vocalizations feasible even for small soundscape-based projects with many rare species. Retraining our open-source model requires only basic programming skills which makes it possible for individual conservation initiatives to match their local context, in order to enable more evidence-informed management of biodiversity.

In this paper we obtain the optimal constants of some classical inequalities, such as the multiple Khinchine inequality for Steinhaus variables and the mixed Littlewood inequality for complex scalars., Comment: 20 pages

Due to diverse nature of data acquisition and modern applications, many contemporary problems involve high dimensional datum $\x \in \R^\d$ whose entries often lie in a union of subspaces and the goal is to find out which entries of $\x$ match with a particular subspace $\sU$, classically called \emph {matched subspace detection}. Consequently, entries that match with one subspace are considered as inliers w.r.t the subspace while all other entries are considered as outliers. Proportion of outliers relative to each subspace varies based on the degree of coordinates from subspaces. This problem is a combinatorial NP-hard in nature and has been immensely studied in recent years. Existing approaches can solve the problem when outliers are sparse. However, if outliers are abundant or in other words if $\x$ contains coordinates from a fair amount of subspaces, this problem can't be solved with acceptable accuracy or within a reasonable amount of time. This paper proposes a two-stage approach called \emph{Greedy Linear Integer Mixed Programmed Selector} (GLIMPS) for this abundant-outliers setting, which combines a greedy algorithm and mixed integer formulation and can tolerate over 80\% outliers, outperforming the state-of-the-art., Comment: 8 pages, 5 figures, 57th Allerton Conference

Using elementary techniques, we prove sharp anisotropic Hardy-Littlewood inequalities for positive multilinear forms. In particular, we recover an inequality proved by F. Bayart in 2018.

Modern inference and learning often hinge on identifying low-dimensional structures that approximate large scale data. Subspace clustering achieves this through a union of linear subspaces. However, in contemporary applications data is increasingly often incomplete, rendering standard (full-data) methods inapplicable. On the other hand, existing incomplete-data methods present major drawbacks, like lifting an already high-dimensional problem, or requiring a super polynomial number of samples. Motivated by this, we introduce a new subspace clustering algorithm inspired by fusion penalties. The main idea is to permanently assign each datum to a subspace of its own, and minimize the distance between the subspaces of all data, so that subspaces of the same cluster get fused together. Our approach is entirely new to both, full and missing data, and unlike other methods, it directly allows noise, it requires no liftings, it allows low, high, and even full-rank data, it approaches optimal (information-theoretic) sampling rates, and it does not rely on other methods such as low-rank matrix completion to handle missing data. Furthermore, our extensive experiments on both real and synthetic data show that our approach performs comparably to the state-of-the-art with complete data, and dramatically better if data is missing.

Completing a data matrix X has become an ubiquitous problem in modern data science, with applications in recommender systems, computer vision, and networks inference, to name a few. One typical assumption is that X is low-rank. A more general model assumes that each column of X corresponds to one of several low-rank matrices. This paper generalizes these models to what we call mixture matrix completion (MMC): the case where each entry of X corresponds to one of several low-rank matrices. MMC is a more accurate model for recommender systems, and brings more flexibility to other completion and clustering problems. We make four fundamental contributions about this new model. First, we show that MMC is theoretically possible (well-posed). Second, we give its precise information-theoretic identifiability conditions. Third, we derive the sample complexity of MMC. Finally, we give a practical algorithm for MMC with performance comparable to the state-of-the-art for simpler related problems, both on synthetic and real data.

In the low-rank matrix completion (LRMC) problem, the low-rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear algebraic variety. This paper extends this thinking to cases where the columns are points on a low-dimensional nonlinear algebraic variety, a problem we call Low Algebraic Dimension Matrix Completion (LADMC). Matrices whose columns belong to a union of subspaces are an important special case. We propose a LADMC algorithm that leverages existing LRMC methods on a tensorized representation of the data. For example, a second-order tensorized representation is formed by taking the Kronecker product of each column with itself, and we consider higher order tensorizations as well. This approach will succeed in many cases where traditional LRMC is guaranteed to fail because the data are low-rank in the tensorized representation but not in the original representation. We provide a formal mathematical justification for the success of our method. In particular, we give bounds of the rank of these data in the tensorized representation, and we prove sampling requirements to guarantee uniqueness of the solution. We also provide experimental results showing that the new approach outperforms existing state-of-the-art methods for matrix completion under a union of subspaces model.

In this work we provide the best constants of the multiple Khintchine inequality. This allows us, among other results, to obtain the best constants of the mixed $\left( \ell_{\frac{p}{p-1}},\ell_{2}\right) $-Littlewood inequality, thus ending completely a work started by Pellegrino in \cite{pell}., Comment: 16 pages

For $p\in\lbrack2,\infty]$ a mixed Littlewood-type inequality asserts that there is a constant $C_{(m),p}\geq1$ such that \[ \left( \sum_{i_{1}=1}^{\infty}\left( \sum_{i_{2},...,i_{m}=1}^{\infty }|T(e_{i_{1}},...,e_{i_{m}})|^{2}\right) ^{\frac{1}{2}\frac{p}{p-1}}\right) ^{\frac{p-1}{p}}\leq C_{(m),p}\Vert T\Vert \] for all continuous real-valued $m$-linear forms on $\ell_{p}\times c_{0} \times\dots\times c_{0}$ (when $p=\infty$, $\ell_{p}$ is replaced by $c_{0})$. We prove that for $p>2.18006$ the optimal constants $C_{(m),p}$ are $\left( 2^{\frac{1}{2}-\frac{1}{p}}\right) ^{m-1}.$ When $p=\infty,$ we recover the best constants of the mixed $\left( \ell_{1},\ell_{2}\right) $-Littlewood inequality., Comment: This new version corresponds to the junction of the previous version with the preprint arXiv:1508.02355. The preprint arXiv:1508.02355 does not exist anymore as a separate preprint

We use the H\"{o}lder inequality for mixed exponents to prove some optimal variants of the generalized Hardy--Littlewood inequality for $m$-linear forms on $\ell _{p}$ spaces with mixed exponents. Our results extend recent results of Araujo et al.

For $p,q\geq2$, the Hardy and Littlewood inequalities for real bilinear forms, in its unified formulation, assert that there is a constant $C_{p,q}\geq1$ such that \begin{equation} \left(\sum\limits_{j=1}^{\infty}\left(\sum\limits_{k=1}^{\infty}\left\vert A(e_{j},e_{k})\right\vert ^{2}\right) ^{\frac{\lambda}{2}}\right) ^{\frac {1}{\lambda}}\leq C_{p,q}\left\Vert A\right\Vert, \end{equation} with sharp exponent $\lambda=\frac{pq}{pq-p-q},$ for all continuous bilinear forms $A:\ell_{p}\times\ell_{q}\rightarrow\mathbb{R}$ (as usual, $c_{0}$ replaces $\ell_{p}$ or $\ell_{q}$ when $p=\infty$ or $q=\infty$)$.$ In this note, among other results, we show that the sharp constants $C_{p,\infty}$ are precisely \[ C_{p,\infty}=2^{\frac{1}{2}-\frac{1}{p}}% \] whenever $p\geq\frac{p_{0}}{p_{0}-1}\approx2.18.$ The number $p_{0}\in(1,2)$ is the unique real number satisfying \[ \Gamma\left(\frac{p_{0}+1}{2}\right) =\frac{\sqrt{\pi}}{2}. \] In the remaining case, i.e., for $2

Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete $d \times N$ matrix is finitely rank-$r$ completable if there are at most finitely many rank-$r$ matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its unique completability. The main contribution of this paper is a deterministic sampling condition for finite completability. We use this to also derive deterministic sampling conditions for unique completability that can be efficiently verified. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if $O(\max\{r,\log d\})$ entries per column are observed. These findings have several implications on LRMC regarding lower bounds, sample and computational complexity, the role of coherence, adaptive settings and the validation of any completion algorithm. We complement our theoretical results with experiments that support our findings and motivate future analysis of uncharted sampling regimes., Comment: This update corrects an error in version 2 of this paper, where we erroneously assumed that columns with more than r+1 observed entries would yield multiple independent constraints

Consider a generic $r$-dimensional subspace of $\mathbb{R}^d$, $r

Give deterministic necessary and sufficient conditions to guarantee that if a subspace fits certain partially observed data from a union of subspaces, it is because such data really lies in a subspace. Furthermore, Give deterministic necessary and sufficient conditions to guarantee that if a subspace fits certain partially observed data, such subspace is unique. Do this by characterizing when and only when a set of incomplete vectors behaves as a single but complete one., Comment: First author mistakenly listed advisors as co-authors in his research proposal. This is corrected in the current version. 59 pages, 19 figures. Subspace clustering, missing data, converse of matrix completion

Recently, in paper published in the Annals of Mathematics, it was shown that the Bohnenblust-Hille inequality for (complex) homogeneous polynomials is hypercontractive. However, and to the best of our knowledge, there is no result providing (nontrivial) lower bounds for the optimal constants for n-homogeneous polynomials (n > 2). In this short note we provide lower bounds for these famous constants.

The power $\frac{2m}{m+1}$ in the polynomial (and multilinear) Bohnenblust--Hille inequality is optimal. This result is well-known but its proof highly nontrivial. In this note we present a quite simple proof of this fact., Comment: This note will be later incorporated in another preprint

The $n$-linear Bohnenblust-Hille inequality asserts that there is a constant $C_{n}\in\lbrack1,\infty)$ such that the $\ell_{\frac{2n}{n+1}}$-norm of $(U(e_{i_{^{1}}},...,e_{i_{n}}))_{i_{1},...i_{n}=1}^{N}$is bounded above by $C_{n}$ times the supremum norm of $U,$ regardless of the $n$-linear form $U:\mathbb{C}^{N}\times...\times\mathbb{C}^{N}% \rightarrow\mathbb{C}$ and the positive integer $N$ (the same holds for real scalars). The power $2n/(n+1)$ is sharp but the values and asymptotic behavior of the optimal constants remain a mystery. The first estimates for these constants had exponential growth. Very recently, a new panorama emerged and the importance, for many applications, of the knowledge of the optimal constants (denoted by $(K_{n})_{n=1}^{\infty}$) was stressed. The title of this paper is part of our Fundamental Lemma, one of the novelties presented here. It brings surprising new (and precise) information on the optimal constants (for both real and complex scalars). For instance, [K_{n+1}-K_{n}<\frac{0.87}{n^{0.473}}] for infinitely many $n$'s. In the case of complex scalars we present a curious formula, where $\pi,e$ and the famous Euler--Mascheroni constant $\gamma$ appear together: [K_{n}<1+(\frac{4}{\sqrt{\pi}}(1-e^{\gamma/2-1/2}) {\sum\limits_{j=1}^{n-1}}j^{^{\log_{2}(e^{-\gamma/2+1/2}) -1}%})] for all $n\geq2$. Numerically, the above formula shows a surprising low growth, [K_{n}<1.41(n-1)^{0.305}-0.04] for every integer $n \geq2$. We also provide a brief discussion on the interplay between the Kahane-Salem-Zygmund and the Bohnenblust-Hille (polynomial and multilinear) inequalities., Comment: An Appendix was added

Let $(K_{n})_{n=1}^{\infty}$ be the optimal constants satisfying the multilinear (real or complex) Bohnenblust--Hille inequality. The exact values of the constants $K_{n}$ are still waiting to be discovered since eighty years ago; recently, it was proved that $(K_{n})_{n=1}^{\infty}$ has a subexponential growth. In this note we go a step further and address the following question: Is it true that \[ \lim_{n\rightarrow\infty}(K_{n}-K_{n-1}) =0? \] Our main result is a Dichotomy Theorem for the constants satisfying the Bohnenblust--Hille inequality; in particular we show that the answer to the above problem is essentially positive in a sense that will be clear along the note. Another consequence of the dichotomy proved in this note is that $(K_{n})_{n=1}^{\infty}$ has a kind of subpolynomial growth: if $p(n)$ is any non-constant polynomial, then $K_{n}$ \textit{is} \textit{not} asymptotically equal to $p(n).$ Moreover, if \[ q>\log_{2}(\frac{e^{1-1/2\gamma}}{\sqrt{2}}) \approx0.526, \] then \[ K_{n}\nsim n^{q}. \]