Improved Top-N recommendations with novel rank approximation.
problem Low accuracy in recommender systems.
method Linear sparse and low-rank representation with nuclear norm relaxation.
result Significantly improved Top-N recommendation accuracy.
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,341 papers · 148 categories
Trend · papers per month
48 results for “rank relaxation”
Paper introduces new norms for rank-constrained optimization problems.
problem Rank-constrained optimization problems in various fields.
method Introduces a family of low-rank inducing norms and regularizers.
result Other low-rank inducing norms outperform nuclear norm in matrix completion problems.
New approach to convex hulls for low-rank problems.
problem Characterizing convex hulls for low-rank sets.
method Matrix perspective function and orthogonal projection matrices.
result Strong relaxations for various low-rank problems.
Paper proposes a new convex relaxation for low-rank approximation problems.
problem Finding low-rank approximations with convex constraints in data analysis.
method Proposes a new convex relaxation using the convex envelope of the squared Frobenius norm and rank constraint.
result Solutions to the convex relaxation coincide with the original non-convex problem under certain conditions.
SGD with mini-batches can solve convex low-rank matrix problems efficiently.
problem Solving large-scale convex low-rank matrix problems efficiently.
method Stochastic Gradient Descent with mini-batches and low-rank projections.
result SGD with mini-batches produces low-rank iterates with high probability.
Paper improves understanding of noisy matrix completion using convex relaxation and nonconvex optimization.
problem Estimating a low-rank matrix from noisy partial entries.
method Combining convex relaxation and the nonconvex Burer-Monteiro approach.
result Convex relaxation achieves near-optimal estimation errors for noisy matrix completion.
Differentiable sorting and rank normalization are incompatible, with specific conditions for admissibility.
problem Incompatibility between differentiable sorting and rank normalization.
method Formalized admissibility through monotone invariance, batch independence, and rank-space stability conditions.
result Different gap-sensitive and batchwise relaxations of rank normalization violate the conditions for admissibility.
New method decomposes corrupted data matrices into sparse and low-rank components.
problem Decomposing corrupted data matrices into sparse and low-rank components.
method Discrete optimization approach with alternating minimization, semidefinite relaxation, and branch-and-bound algorithm.
result High-quality solutions and meaningful bounds for SLR problems.
Paper proposes efficient algorithm for non-convex rank minimization.
problem Efficiently solving rank minimization problems with non-convex penalties.
method Iterative Shrinkage-Thresholding Algorithm (ISTA) for non-convex weighted and reweighted nuclear norm.
result Proves convergence to critical point with rate and outperforms state-of-the-art methods.
SyncRank recovers global ranking from noisy comparisons with theoretical guarantees.
problem Recovering a global ranking from noisy pairwise comparisons.
method Complex-valued data model and SDP relaxation for exact ranking recovery.
result SyncRank achieves exact ranking recovery with high probability above a critical noise threshold of O(sqrt(n / log n)).
Improved Top-N recommender system using matrix completion.
problem Low-quality Top-N recommendations.
method Low-rank matrix completion with nonconvex rank relaxation and efficient optimization.
result Significantly improved Top-N recommendation accuracy.
We show that the spectral norm of a random tensor (or higher-order array) scales as under some sub-Gaussian assumption on the entries. The proof is based on a covering number argument. Since the spectral norm is dual to the tensor…
New method solves matrix completion problems to certifiable optimality.
problem Certifying optimality in low-rank matrix completion.
method Disjunctive branch-and-bound scheme for convex relaxation.
result Decreases optimality gap by two orders of magnitude.
New framework solves low-rank optimization problems to certifiable optimality.
problem Low-rank optimization problems with certifiable solutions.
method Mixed-Projection Conic Optimization framework using symmetric projection matrices and outer-approximation algorithms.
result Solves low-rank problems to certifiable optimality, outperforming existing methods.
Exact recovery of low-rank matrices from few entries improved with relaxed leverage sampling.
problem Exact recovery of low-rank matrices from a small number of observed entries.
method Sampling probabilities proportional to the sum of leverage scores minus their product.
result Exact recovery with fewer entries than previously possible, matching theoretical lower bounds.
The paper tackles preference prediction from ordinal data.
problem Predicting preferences from ordinal data collected in various forms.
method Solves a convex relaxation of nuclear norm minimization to learn the underlying low-rank model.
result The convex relaxation approach is minimax optimal and provides upper and lower bounds on error.
Paper proposes a new method to separate low rank and sparse matrices without bias.
problem Recovering low rank and sparse matrices from measurements.
method Uses nonconvex regularizers and alternating proximal gradient descent.
result Error bounds for the algorithm applied to sparse optimization, matrix completion, and robust PCA.
New conditions ensure Dantzig-Wolfe relaxation matches rank-constrained optimization problems.
problem Rank-constrained optimization problems with linear matrix inequalities.
method Investigates Dantzig-Wolfe relaxation and develops conditions for exactness.
result Conditions for extreme point, convex hull, and objective exactness.
New convex relaxations solve sparse regression problems efficiently.
problem Sparse regression with constraint is NP-hard.
method Rank-one convexification for semidefinite optimization.
result Stronger and more general convex relaxations for sparse regression.
New algorithm for low-rank optimal transport with improved interpretability and efficiency.
problem Quadratic scaling of optimal transport coupling matrix for massive datasets.
method Factor Relaxation with Latent Coupling (FRLC) algorithm.
result Superior performance on diverse applications including graph clustering and spatial transcriptomics.
STARK learns structured dictionaries for tensor data.
problem Representing multidimensional data with structured dictionaries.
method Solves a convex relaxation of a nonconvex rank-1 tensor recovery problem.
result Empirical results show promising performance for tensors of any order.
New method solves nonsmooth low-rank matrix optimization problems efficiently.
problem Nonsmooth and low-rank matrix optimization problems in statistics and machine learning.
method Low-rank Extragradient Method with warm-start initialization.
result The extragradient method converges to an optimal solution with rate and requires only two low-rank SVDs per iteration.
New algorithm for weighted low rank approximation with provable guarantees.
problem Weighted low rank approximation (WLRA) is computationally hard.
method Reweights the low rank solution using the weight matrix itself.
result Provably optimal approximation guarantees for WLRA.
New nonconvex regularizers improve low-rank matrix recovery efficiency and accuracy.
problem Efficiently recover low-rank matrices from incomplete data.
method Factor group-sparse regularization, related to Schatten-p norms.
result Improved generalization error bounds for Schatten-p norms as p decreases.
New method closes certification gap for adversarially trained models.
problem Certifying robustness of adversarially trained neural networks.
method Nonconvex low-rank SDP relaxation with polynomial-time optimization.
result Strong certifications comparable to SDP methods, but with fewer variables.
New method relaxes spatial invariance in locally connected layers, improving accuracy.
problem Improving classification accuracy with locally connected layers.
method Designing a low-rank locally connected layer with varying spatially varying combining weights.
result Relaxing spatial invariance improves classification accuracy over convolution and locally connected layers.
Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recov…
TeaNet: universal neural network interatomic potential inspired by iterative electronic relaxationsphysics.comp-ph
TeaNet uses GCNs to model complex atomic interactions inspired by electronic relaxation.
problem Creating a universal interatomic potential for all elements.
method Tensor-embedded atom network (TeaNet) using graph convolutional neural networks (GCNs).
result TeaNet achieves good performance (19 meV/atom) for structures and reactions involving elements from H to Ar.
The problem of low-rank matrix estimation recently received a lot of attention due to challenging applications. A lot of work has been done on rank-penalized methods and convex relaxation, both on the theoretical and applied sides. However, only a few papers considered Bayesian estimation. In this paper, we review the …
Solves ranking problems with noisy data using synchronization techniques.
problem Establishing rankings from inconsistent and incomplete comparisons.
method Formulates as group synchronization problem, uses spectral or SDP relaxation followed by rounding.
result Proposed method outperforms other algorithms in simulations.
Proximal splitting methods solve rank-constrained convex problems locally.
problem Solving optimization problems with rank constraints.
method Proximal splitting algorithms with conditions on rank constraint convex envelopes.
result Proximal splitting methods converge locally to solutions under convex relaxation conditions.
This paper tackles poor approximations in learning-to-rank algorithms and proposes exact reranking methods.
problem Poor approximations in learning-to-rank algorithms based on convex proxies.
method Exact reranking algorithms based on mathematical programming.
result A relaxed version of the exact problem has the same optimal solution.
The paper develops methods to optimize ranking metrics for hashing.
problem Improving hashing for better retrieval performance.
method Developed tie-aware learning to rank formulations for hashing.
result Established new state-of-the-art for image retrieval by Hamming ranking.
Paper proposes a new matrix recovery method relaxing uniform sampling assumptions.
problem Matrix completion under arbitrary sampling schemes.
method Max-norm and nuclear-norm regularization, alternating direction method of multipliers.
result The proposed method achieves fast rates of convergence and is computationally efficient.
Paper improves EEG signal reconstruction efficiency and accuracy.
problem No good sparse representation and high computational cost in multi-channel EEG signals.
method Proposes an optimization model with L0 norm and Schatten-0 norm for cosparsity and low rank structures, using convex relaxation and alternating direction method of multipliers.
result Improves multi-channel EEG signal reconstruction in terms of accuracy and computational complexity.
Paper relaxes factor analysis for noisy data, improving robustness.
problem Challenges in finding robust low dimensional approximations for data with heteroskedastic noise.
method Introduces a relaxed version of Minimum Trace Factor Analysis (MTFA) as a convex optimization method.
result Effective at not overfitting to heteroskedastic perturbations and addressing common issues in factor analysis.
A new method improves semidefinite programming performance.
problem Structured semidefinite programming with diagonal constraints.
method Low-rank coordinate descent approach called the Mixing method.
result The Mixing method converges to the global optimum almost surely.
Study infinite subgroups of higher rank Lie groups, focusing on Anosov subgroups.
problem Understanding properties of Anosov subgroups in higher rank semisimple Lie groups.
method Characterize Anosov subgroups through geometric, coarse geometric, and dynamical viewpoints.
result New equivalent characterizations of Anosov subgroups, capturing rank one behavior.
Differentiable relaxation for inferring partial orders from noisy linear data.
problem Inference of partial orders from linear data with noisy observations.
method Introducing a differentiable relaxation to model noisy linear extensions, replacing discontinuous precedence and feasibility with smooth surrogates.
result Smooth posterior that preserves partial-order semantics, supports gradient-based inference, and converges to hard likelihood.
Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions,…
On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examplesmath.OC
Geometric technique determines exactness of SDP robustness certificate.
problem Certifying robustness of neural networks to adversarial examples.
method Geometric projection onto hyperbola, SDP relaxation of ReLU activation.
result SDP certificate is exact for a single hidden layer under mild assumptions.
Paper tackles missing value imputation in time series forecasting.
problem Missing value imputation in time series analysis.
method Low-rank matrix completion with Hankel matrices and nuclear norm relaxation.
result Proper weighting scheme is crucial for known observations.
Globally optimized SVD compression of LLMs via Fermi-function-based rank selection and gauge fixingcs.LG
Physics-inspired methods optimize SVD compression of LLMs.
problem Efficiently compressing large language models (LLMs) using SVD.
method FermiGrad for globally optimal rank selection and PivGa for lossless compression.
result Global optimization of SVD ranks and lossless compression of low-rank factors.
EM optimizes tensor density estimation by relaxing -divergence to KL-divergence.
problem Analytical challenges in traditional -divergence optimization for tensor-based density estimation.
method EM algorithm: relaxes optimization to KL-divergence, then applies tensor many-body approximation.
result Flexible modeling of various low-rank structures and their mixtures.
We study the problem of collaborative filtering where ranking information is available. Focusing on the core of the collaborative ranking process, the user and their community, we propose new models for representation of the underlying permutations and prediction of ranks. The first approach is based on the assumption …
Proposes a new rank approximation method for improved subspace clustering accuracy.
problem Improving rank approximation for better subspace clustering accuracy in real-world applications.
method Smoothed rank approximation using Logarithm-Determinant for robust subspace clustering.
result The proposed method outperforms state-of-the-art algorithms in face clustering and motion segmentation tasks.
We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation of the sum of an approximately) low rank matrix with a second matrix endowed with a complementary …
MARS automatically selects tensor decomposition ranks, improving performance in neural network tasks.
problem Determining optimal decomposition ranks in tensor decompositions.
method MARS uses binary masks to learn optimal tensor structure during training via relaxed MAP estimation.
result MARS achieves better results than previous methods in various tasks.