English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper, we study the polynomial approximability or solvability ofsparse integer least square problem (SILS), which is the NP-hard variant of theleast square problem, where we only consider sparse {0, +1, -1}-vectors. Wepropose an l1-based SDP relaxation to SILS, and introduce a randomizedalgorithm for SILS based on the SDP relaxation. In fact, the proposedrandomized algorithm works for a broader class of binary quadratic program withcardinality constraint, where the objective function can be possiblynon-convex. Moreover, when the sparsity parameter is fixed, we providesufficient conditions for our SDP relaxation to solve SILS. The class of datainput which guarantee that SDP solves SILS is broad enough to cover many casesin real-world applications, such as privacy preserving identification, andmultiuser detection. To show this, we specialize our sufficient conditions totwo special cases of SILS with relevant applications: the feature extractionproblem and the integer sparse recovery problem. We show that our SDPrelaxation can solve the feature extraction problem with sub-Gaussian data,under some weak conditions on the second moment of the covariance matrix. Wealso show that our SDP relaxation can solve the integer sparse recovery problemunder some conditions that can be satisfied both in high and low coherencesettings.

An SDP Relaxation for the Sparse Integer Least Square Problem