Publications related to Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Matrix Completion on Graphs

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Vasilis Kalofolias

The problem of finding the missing values of a matrix given a few of its entries, called matrix completion, has gathered a lot of attention in the recent years. Al- though the problem under the standard low rank assumption is NP-hard, Cande`s and Recht sho ...

2014

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Nisheeth Vishnoi

We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n). © 2014 Soc ...

Society for Industrial and Applied Mathematics2014

Tractability of interpretability via selection of group-sparse models

Volkan Cevher, Luca Baldassarre, Nirav Bhan

Group-based sparsity models are proven instrumental in linear regression problems for recovering signals from much fewer measurements than standard compressive sensing. A promise of these models is to lead to “interpretable” signals for which we identify i ...

2013

Testing additive integrality gaps

Friedrich Eisenbrand, Gennady Shmonin

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in ...

Springer Berlin Heidelberg2013

TCHo: A Code-Based Cryptosystem

Serge Vaudenay, Alexandre Raphaël Duc

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz ...

Springer Berlin Heidelberg2013

Hessian Schatten-Norm Regularization for Linear Inverse Problems

Michaël Unser, John Paul Ward, Stamatios Lefkimmiatis

We introduce a novel family of invariant, convex, and non-quadratic functionals that we employ to derive regularized solutions of ill-posed linear inverse imaging problems. The proposed regularizers involve the Schatten norms of the Hessian matrix, which a ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Sponsored search, market equilibria, and the Hungarian Method

Monika Henzinger, Ingmar Weber

Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settin ...

Elsevier Science Bv2013

Santa Claus Schedules Jobs On Unrelated Machines

Ola Nils Anders Svensson

One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...

Siam Publications2012

Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence

Graph Chatbot

Chat with Graph Search

Matrix Completion on Graphs

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Tractability of interpretability via selection of group-sparse models

Testing additive integrality gaps

Single machine scheduling with scenarios

TCHo: A Code-Based Cryptosystem

Decomposition and tractability in qualitative spatial and temporal reasoning

Hessian Schatten-Norm Regularization for Linear Inverse Problems

Sponsored search, market equilibria, and the Hungarian Method

Santa Claus Schedules Jobs On Unrelated Machines

Single machine scheduling with scenarios

TCHo: A Code-Based Cryptosystem

Hessian Schatten-Norm Regularization for Linear Inverse Problems

Tractability of interpretability via selection of group-sparse models

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

Decomposition and tractability in qualitative spatial and temporal reasoning

Matrix Completion on Graphs

Santa Claus Schedules Jobs On Unrelated Machines

Testing additive integrality gaps

Sponsored search, market equilibria, and the Hungarian Method