DeepHull: Fast Convex Hull Approximation in High Dimensions
Computing or approximating the convex hull of a dataset plays a role in a wide range of applications, including economics, statistics, and physics, to name just a few. However, convex hull computation and approximation is exponentially complex, in terms of both memory and computation, as the ambient space dimension increases. In this paper, we propose DeepHull, a new convex hull approximation algorithm based on convex deep networks (DNs) with continuous piecewise-affine nonlinearities and nonnegative weights. The idea is that binary classification between true data samples and adversarially generated samples with such a DN naturally induces a polytope decision boundary that approximates the true data convex hull. A range of exploratory experiments demonstrates that DeepHull efficiently produces a meaningful convex hull approximation, even in a high-dimensional ambient space.
Authors:
; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10371730
Journal Name:
ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
2. Summary This paper is concerned with empirical likelihood inference on the population mean when the dimension $p$ and the sample size $n$ satisfy $p/n\rightarrow c\in [1,\infty)$. As shown in Tsao (2004), the empirical likelihood method fails with high probability when $p/n>1/2$ because the convex hull of the $n$ observations in $\mathbb{R}^p$ becomes too small to cover the true mean value. Moreover, when $p> n$, the sample covariance matrix becomes singular, and this results in the breakdown of the first sandwich approximation for the log empirical likelihood ratio. To deal with these two challenges, we propose a new strategy of adding two artificial data points to the observed data. We establish the asymptotic normality of the proposed empirical likelihood ratio test. The proposed test statistic does not involve the inverse of the sample covariance matrix. Furthermore, its form is explicit, so the test can easily be carried out with low computational cost. Our numerical comparison shows that the proposed test outperforms some existing tests for high-dimensional mean vectors in terms of power. We also illustrate the proposed procedure with an empirical analysis of stock data.
{"ft_lang_label":"__label__en","ft_lang_prob":0.90463734,"math_prob":0.92333186,"size":6826,"snap":"2023-14-2023-23","text_gpt3_token_len":1325,"char_repetition_ratio":0.11844034,"word_repetition_ratio":0.0,"special_character_ratio":0.18370935,"punctuation_ratio":0.06678383,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9805359,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-03T05:48:39Z\",\"WARC-Record-ID\":\"<urn:uuid:0e333c4d-11e0-4696-8d11-baa496f23b30>\",\"Content-Length\":\"239502\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:605eafab-7b3e-4a7e-aa23-acdf3b5a0f0d>\",\"WARC-Concurrent-To\":\"<urn:uuid:185043e3-2a6e-4a7f-9fe9-f352d6e8629d>\",\"WARC-IP-Address\":\"192.107.175.180\",\"WARC-Target-URI\":\"https://par.nsf.gov/biblio/10371730-deephull-fast-convex-hull-approximation-high-dimensions\",\"WARC-Payload-Digest\":\"sha1:4JLHEYTK5DZF6RMDO5H2S3BCPT5JZIIZ\",\"WARC-Block-Digest\":\"sha1:GJI35TC5CS3HH7F3AWI53R4Y52GKG2X6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224649105.40_warc_CC-MAIN-20230603032950-20230603062950-00145.warc.gz\"}"}